32. FOCS 1991: San Juan, Puerto Rico
32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991. IEEE Computer Society 1991- 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
- 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
- Jeffrey Scott Vitter, P. Krishnan: Optimal Prefetching via Data Compression (Extended Abstract). 121-130
- Manfred Kunde: Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound. 141-150
- 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
- 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
- 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, 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
- 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
- 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
- Peter W. Shor: How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing. 752-759
- 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
- Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen: On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract). 793-801
- Harold N. Gabow: Applications of a Poset Representation to Edge Connectivity and Graph Rigidity. 812-821
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team