33. FOCS 1992: Pittsburgh, Pennsylvania, USA

• Sanjeev Arora, Shmuel Safra:
  Probabilistic Checking of Proofs; A New Characterization of NP. 2-13
  
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
  Proof Verification and Hardness of Approximation Problems. 14-23
  
• Noam Nisan, Endre Szemerédi, Avi Wigderson:
  Undirected Connectivity in O(log ^1.5 n) Space. 24-29
  
• Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
  The Isomorphism Conjecture Holds Relative to an Oracle. 30-39
  
• Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
  Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues. 40-49
  
• Monika Rauch:
  Fully Dynamic Biconnectivity in Graphs. 50-59
  
• David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig:
  Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract). 60-69
  
• Tsan-sheng Hsu:
  On Four-Connecting a Triconnected Graph (Extended Abstract). 70-79
  
• Pankaj K. Agarwal, David Eppstein, Jirí Matousek:
  Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees. 80-89
  
• Ketan Mulmuley:
  Randomized Geometric Algorithms and Pseudo-Random Generators (Extended Abstract). 90-100
  
• Goos Kant:
  Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract). 101-110
  
• Eugene M. Luks:
  Computing in Solvable Matrix Groups. 111-120
  
• Mark Giesbrecht:
  Fast Algorithms for Matrix Normal Forms. 121-130
  
• Dario Bini, Victor Y. Pan:
  Improved Parallel Polynomial Division and Its Extensions. 131-136
  
• James Aspnes, Orli Waarts:
  Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor. 137-146
  
• Yonatan Aumann, Michael O. Rabin:
  Clock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation (Extended Abstract). 147-156
  
• Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg:
  Fault-tolerant Wait-free Shared Objects. 157-166
  
• Erich Grädel, Gregory L. McColm:
  Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. 167-176
  
• Rajeev Alur, Thomas A. Henzinger:
  Back to the Future: Towards a Theory of Timed Regular Languages. 177-186
  
• Toniann Pitassi, Alasdair Urquhart:
  The Complexity of the Hajós Calculus. 187-196
  
• Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
  A Decomposition Theorem and Bounds for Randomized Server Problems. 197-207
  
• Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan:
  Markov Paging (Extended Abstract). 208-217
  
• Yossi Azar, Andrei Z. Broder, Anna R. Karlin:
  On-line Load Balancing (Extended Abstract). 218-225
  
• C. Greg Plaxton, Bjorn Poonen, Torsten Suel:
  Improved Lower Bounds for Shellsort. 226-235
  
• Peter Bro Miltersen, Mike Paterson, Jun Tarui:
  The Asymptotic Complexity of Merging Networks. 236-246
  
• Zvi Galil, Kunsoo Park:
  Truly Alphabet-Independent Two-Dimensional Pattern Matching. 247-256
  
• Moshe Dubiner, Uri Zwick:
  Amplification and Percolation. 258-267
  
• Andrew Chi-Chih Yao:
  Algebraic Decision Trees and Euler Characteristics. 268-277
  
• Vince Grolmusz:
  Separating the Communication Complexities of MOD m and MOD p Circuits. 278-287
  
• Don Coppersmith, Baruch Schieber:
  Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary). 288-295
  
• Nabil Kahale:
  On the Second Eigenvalue and Linear Expansion of Regular Graphs. 296-303
  
• Yuri Rabinovich, Alistair Sinclair, Avi Wigderson:
  Quadratic Dynamical Systems (Preliminary Version). 304-313
  
• Joel Friedman:
  On the Bit Extraction Problem. 314-319
  
• Mark Jerrum, Umesh V. Vazirani:
  A Mildly Exponential Approximation Algorithm for the Permanent. 320-326
  
• Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin:
  Competitive Analysis of Financial Games. 327-333
  
• Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer:
  Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract). 334-343
  
• Yair Bartal, Adi Rosén:
  The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms. 344-353
  
• Jerzy Marcinkowski, Leszek Pacholski:
  Undecidability of the Horn-Clause Implication Problem. 354-362
  
• Dexter Kozen, Jens Palsberg, Michael I. Schwartzbach:
  Efficient Inference of Partial Types. 363-371
  
• Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens:
  On the Completeness of Object-Creating Query Languages (Extended Abstract). 372-379
  
• Hans-Peter Lenhof, Michiel H. M. Smid:
  Enumerating the k Closest Pairs Optimally. 380-386
  
• Kenneth L. Clarkson:
  Safe and Effective Determinant Evaluation. 387-395
  
• Naoki Katoh, Takeshi Tokuyama, Kazuo Iwano:
  On Minimum and Maximum Spanning Trees of Linearly Moving Points. 396-405
  
• Manuel Blum, Oded Goldreich:
  Towards a Computational Theory of Statistical Tests (Extended Abstract). 406-416
  
• Noga Alon, Zvi Galil, Oded Margalit, Moni Naor:
  Witnesses for Boolean Matrix Multiplication and for Shortest Paths. 417-426
  
• Alfredo De Santis, Giuseppe Persiano:
  Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract). 427-436
  
• Chee-Keng Yap:
  Fast Unimodular Reduction: Planar Integer Lattices (Extended Abstract). 437-446
  
• Johannes Blömer:
  How to Denest Ramanujan's Nested Radicals. 447-456
  
• Wayne Eberly:
  On Efficient Band Matrix Arithmetic. 457-463
  
• Bernd Gärtner:
  A Subexponential Algorithm for Abstract Optimization Problems. 464-472
  
• Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rödl, Raphael Yuster:
  The Algorithmic Aspects of the Regularity Lemma (Extended Abstract). 473-481
  
• László Lovász, Miklós Simonovits:
  On the Randomized Complexity of Volume and Diameter. 482-491
  
• David P. Helmbold, Nick Littlestone, Philip M. Long:
  Apple Tasting and Nearly One-Sided Learning. 493-502
  
• Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
  Reconstructing Algebraic Functions from Mixed Data. 503-512
  
• Nader H. Bshouty, Richard Cleve:
  On the Exact Learning of Formulas in Parallel (Extended Abstract). 513-522
  
• Howard Aizenstein, Lisa Hellerstein, Leonard Pitt:
  Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries. 523-532
  
• Hisao Tamaki:
  Efficient Self-Embedding of Butterfly Networks with Random Faults. 533-541
  
• Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman:
  On the Fault Tolerance of Some Popular Bounded-Degree Networks. 542-552
  
• Uriel Feige, Prabhakar Raghavan:
  Exact Analysis of Hot-Potato Routing (Extended Abstract). 553-562
  
• Sergio A. Felperin, Prabhakar Raghavan, Eli Upfal:
  A Theory of Wormhole Routing in Parallel Computers (Extended Abstract). 563-572
  
• Joseph S. B. Mitchell, Christine D. Piatko, Esther M. Arkin:
  Computing a Shortest k-Link Path in a Polygon. 573-582
  
• Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber:
  Efficient Minimum Cost Matching Using Quadrangle Inequality. 583-592
  
• Hubert Wagener:
  Optimal Parallel Hull Construction for Simple Polygons in \calO(log log n) Time. 593-599
  
• Richard Cole, Ramesh Hariharan:
  Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract). 600-609
  
• Claire Kenyon, Richard Kenyon:
  Tiling a Polygon with Rectangles. 610-619
  
• Vasek Chvátal, Bruce A. Reed:
  Mick Gets Some (the Odds Are on His Side). 620-627
  
• Torben Hagerup, Rajeev Raman:
  Waste Makes Haste: Tight Bounds for Loose Parallel Sorting. 628-637
  
• Shiva Chaudhuri, Jaikumar Radhakrishnan:
  The Complexity of Parallel Prefix Problems on Small Domains. 638-647
  
• Edith Cohen:
  Approximate Max Flow on Small Depth Networks. 648-658
  
• Tomasz Radzik:
  Newton's Method for Fractional Combinatorial Optimization. 659-669
  
• Michele Conforti, Gérard Cornuéjols:
  A Class of Logic Problems Solvable by Linear Programming. 670-675
  
• Sivan Toledo:
  Maximizing Non-Linear Concave Functions in Fixed Dimension. 676-685
  
• Miklós Ajtai, János Komlós, Endre Szemerédi:
  Halvers and Expanders. 686-692
  
• Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi:
  Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths. 693-702
  
• Victor Y. Pan, John H. Reif, Stephen R. Tate:
  The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms. 703-713
  
• Erich Kaltofen, Victor Y. Pan:
  Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract). 714-723
  
• Leonard J. Schulman:
  Communication on Noisy Channels: A Coding Theorem for Computation. 724-733
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page