32. FOCS 1991: San Juan, Puerto Rico

• Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
  Approximating Clique is Almost NP-Complete (Preliminary Version). 2-12
  
• Dror Lapidot, Adi Shamir:
  Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract). 13-18
  
• Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser:
  Languages that Are Easier than their Proofs. 19-28
  
• Bernard Chazelle:
  An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract). 29-38
  
• Frank Hoffmann, Michael Kaufmann, Klaus Kriegel:
  The Art Gallery Theorem for Polygons With Holes. 39-48
  
• Jirí Matousek, Nathaly Miller, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl:
  Fat Triangles Determine Linearly Many Holes. 49-58
  
• Oded Goldreich, Erez Petrank:
  Quantifying Knowledge Complexity. 59-68
  
• Joan Boyar, Gilles Brassard, René Peralta:
  Subquadratic Zero-Knowledge. 69-78
  
• David Zuckerman:
  Simulating BPP Using a General Weak Random Source. 79-89
  
• Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor:
  Checking the Correctness of Memories. 90-99
  
• Sanjoy K. Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis Shasha:
  On-line Scheduling in the Presence of Overload. 100-110
  
• Anja Feldmann, Jiri Sgall, Shang-Hua Teng:
  Dynamic Scheduling on Parallel Machines. 111-120
  
• Jeffrey Scott Vitter, P. Krishnan:
  Optimal Prefetching via Data Compression (Extended Abstract). 121-130
  
• David B. Shmoys, Joel Wein, David P. Williamson:
  Scheduling Parallel Machines On-Line. 131-140
  
• Manfred Kunde:
  Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound. 141-150
  
• I-Chen Wu, H. T. Kung:
  Communication Complexity for Parallel Divide-and-Conquer. 151-162
  
• Christos H. Papadimitriou:
  On Selecting a Satisfying Truth Assignment (Extended Abstract). 163-169
  
• Howard Aizenstein, Leonard Pitt:
  Exact Learning of Read-Twice DNF Formulas (Extended Abstract). 170-179
  
• Ketan Mulmuley:
  Randomized Multidimensional Search Trees: Lazy Balancing and Dynamic Shuffling (Extended Abstract). 180-196
  
• Otfried Schwarzkopf:
  Dynamic Maintenance of Geometric Structures Made Easy. 197-206
  
• Jirí Matousek:
  Reporting Points in Halfspaces. 207-215
  
• Ketan Mulmuley:
  Randomized Multidimensional Search Trees: Further Results in Dynamic Sampling (Extended Abstract). 216-227
  
• Alon Orlitsky:
  Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity. 228-238
  
• Tomás Feder, Eyal Kushilevitz, Moni Naor:
  Amortized Communication Complexity (Preliminary Version). 239-248
  
• Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall:
  Communication Complexity Towards Lower Bounds on Circuit Depth. 249-257
  
• Baruch Awerbuch, George Varghese:
  Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract). 258-267
  
• Baruch Awerbuch, Boaz Patt-Shamir, George Varghese:
  Self-Stabilization By Local Checking and Correction (Extended Abstract). 268-277
  
• Weiguo Wang:
  An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton. 278-285
  
• Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan:
  Competitive Algorithms for Layered Graph Traversal. 288-297
  
• Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
  How to Learn an Unknown Environment (Extended Abstract). 298-303
  
• Rolf Klein:
  Walking an Unknown Street with Bounded Detour. 304-313
  
• Jaikumar Radhakrishnan:
  Better Bounds for Threshold Formulas. 314-323
  
• Mike Paterson, Uri Zwick:
  Shrinkage of de~Morgan formulae under restriction. 324-333
  
• Nader H. Bshouty, Richard Cleve, Wayne Eberly:
  Size-Depth Tradeoffs for Algebraic Formulae. 334-341
  
• Bruce M. Kapron, Stephen A. Cook:
  A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract). 342-347
  
• Rakesh M. Verma:
  A Theory of Using History for Equational Systems with Applications (Extended Abstract). 348-357
  
• Nils Klarlund:
  Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic. 358-367
  
• E. Allen Emerson, Charanjit S. Jutla:
  Tree Automata, Mu-Calculus and Determinacy (Extended Abstract). 368-377
  
• Victor Shoup, Roman Smolensky:
  Lower Bounds for Polynomial Evaluation and Interpolation Problems. 378-383
  
• Joachim von zur Gathen:
  Efficient Exponentiation in Finite Fields (Extended Abstract). 384-391
  
• Moshe Morgenstern:
  Explicit Construction of Natural Bounded Concentrators. 392-397
  
• Nabil Kahale:
  Better Expansion for Ramanujan Graphs. 398-404
  
• Ioannis Z. Emiris, John F. Canny:
  A General Approach to Removing Degeneracies. 405-413
  
• Herbert Edelsbrunner, Tiow Seng Tan:
  A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract). 414-423
  
• Jirí Matousek, Emo Welzl, Lorenz Wernisch:
  Discrepancy and epsilon-approximations for bounded VC-dimension. 424-430
  
• Ding-Zhu Du, Yanjun Zhang, Qing Feng:
  On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract). 431-439
  
• Yonatan Aumann, Michael Ben-Or:
  Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract). 440-446
  
• Oded Goldreich, Shafi Goldwasser, Nathan Linial:
  Fault-tolerant Computation in the Full Information Model (Extended Abstract). 447-457
  
• Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton:
  Highly Fault-Tolerant Sorting Circuits. 458-469
  
• Frank Thomson Leighton, Eric J. Schwabe:
  Efficient Algorithms for Dynamic Allocation of Distributed Memory. 470-479
  
• Ilan Adler, Peter A. Beling:
  Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices. 480-487
  
• David Eppstein:
  Dynamic Three-Dimensional Linear Programming. 488-494
  
• Serge A. Plotkin, David B. Shmoys, Éva Tardos:
  Fast Approximation Algorithms for Fractional Packing and Covering Problems. 495-504
  
• Baruch Awerbuch, Leonard J. Schulman:
  The Maintenance of Common Data in a Distributed System. 505-514
  
• Moni Naor, Ron M. Roth:
  Optimal File Sharing in Distributed Networks (Preliminary Version). 515-525
  
• Maurice Herlihy, Nir Shavit, Orli Waarts:
  Low Contention Linearizable Counting. 526-535
  
• Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis:
  A Unified Geometric Approach to Graph Separators. 538-547
  
• Tsan-sheng Hsu, Vijaya Ramachandran:
  A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract). 548-559
  
• David R. Karger, Daphne Koller, Steven J. Phillips:
  Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths. 560-568
  
• Noga Alon, Zvi Galil, Oded Margalit: On the Exponent of the All Pairs Shortest Path Problem. 569-575
• László Lovász, Moni Naor, Ilan Newman, Avi Wigderson:
  Search Problems in the Decision Tree Model (Preliminary Version). 576-585
  
• Noga Alon:
  A parallel algorithmic version of the Local Lemma. 586-593
  
• Anna Gál:
  Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates. 594-601
  
• Rüdiger Reischuk, Bernd Schmeltz:
  Reliable Computation with Noisy Circuits and Decision Trees-A General n log n Lower Bound. 602-611
  
• Rajamani Sundar:
  A Lower Bound for the Dictionary Problem under a Hashing Model. 612-621
  
• Amir M. Ben-Amram, Zvi Galil:
  Lower Bounds for Data Structure Problems on RAMs (Extended Abstract). 622-631
  
• Greg N. Frederickson:
  Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees. 632-641
  
• Arne Andersson, Thomas Ottmann:
  Faster Uniquely Represented Dictionaries. 642-649
  
• Bruce Randall Donald, Davied Renpan Chang:
  On the Complexity of Computing the Homology Type of a Triangulation. 650-661
  
• Dima Grigoriev, Marek Karpinski:
  An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]. 662-669
  
• Johannes Blömer:
  Computing Sums of Radicals in Polynomial Time. 670-677
  
• Ming-Deh A. Huang, Doug Ierardi:
  Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve (Extended Abstract). 678-687
  
• Donald B. Johnson, Panagiotis Takis Metaxas:
  Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM. 688-697
  
• Joseph Gil, Yossi Matias, Uzi Vishkin:
  Towards a Theory of Nearly Constant Time Parallel Algorithms. 698-710
  
• Michael T. Goodrich:
  Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version). 711-722
  
• Hillel Gazit:
  A Deterministic Parallel Algorithm for Planar Graphs Isomorphism. 723-732
  
• László Babai, Katalin Friedl:
  Approximate Representation Theory of Finite Groups. 733-742
  
• Huzur Saran, Vijay V. Vazirani:
  Finding k-cuts within Twice the Optimal. 743-751
  
• Peter W. Shor:
  How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing. 752-759
  
• Amihood Amir, Martin Farach:
  Adaptive Dictionary Matching. 760-766
  
• Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag:
  On the Computational Power of Sigmoid versus Boolean Threshold Circuits. 767-776
  
• Matthias Krause, Stephan Waack:
  Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fan-In. 777-782
  
• Richard Beigel, Jun Tarui:
  On ACC. 783-792
  
• Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen:
  On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract). 793-801
  
• Arvind Gupta, Russell Impagliazzo:
  Computing Planar Intertwines. 802-811
  
• Harold N. Gabow:
  Applications of a Poset Representation to Edge Connectivity and Graph Rigidity. 812-821
  

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