| 1991 | 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1-4, 1991 |
| 1991 | A Deterministic Parallel Algorithm for Planar Graphs Isomorphism Hillel Gazit |
| 1991 | A General Approach to Removing Degeneracies Ioannis Z. Emiris, John F. Canny |
| 1991 | A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract) Tsan-sheng Hsu, Vijaya Ramachandran |
| 1991 | A Lower Bound for the Dictionary Problem under a Hashing Model Rajamani Sundar |
| 1991 | A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) Bruce M. Kapron, Stephen A. Cook |
| 1991 | A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract) Herbert Edelsbrunner, Tiow Seng Tan |
| 1991 | A Theory of Using History for Equational Systems with Applications (Extended Abstract) Rakesh M. Verma |
| 1991 | A Unified Geometric Approach to Graph Separators Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis |
| 1991 | A parallel algorithmic version of the Local Lemma Noga Alon |
| 1991 | Adaptive Dictionary Matching Amihood Amir, Martin Farach |
| 1991 | Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees Greg N. Frederickson |
| 1991 | Amortized Communication Complexity (Preliminary Version) Tomás Feder, Eyal Kushilevitz, Moni Naor |
| 1991 | An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] Dima Grigoriev, Marek Karpinski |
| 1991 | An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton Weiguo Wang |
| 1991 | An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract) Bernard Chazelle |
| 1991 | Applications of a Poset Representation to Edge Connectivity and Graph Rigidity Harold N. Gabow |
| 1991 | Approximate Representation Theory of Finite Groups László Babai, Katalin Friedl |
| 1991 | Approximating Clique is Almost NP-Complete (Preliminary Version) Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy |
| 1991 | Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract) Yonatan Aumann, Michael Ben-Or |
| 1991 | Better Bounds for Threshold Formulas Jaikumar Radhakrishnan |
| 1991 | Better Expansion for Ramanujan Graphs Nabil Kahalé |
| 1991 | Checking the Correctness of Memories Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor |
| 1991 | Communication Complexity Towards Lower Bounds on Circuit Depth Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jirí Sgall |
| 1991 | Communication Complexity for Parallel Divide-and-Conquer I-Chen Wu, H. T. Kung |
| 1991 | Competitive Algorithms for Layered Graph Traversal Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan |
| 1991 | Computing Planar Intertwines Arvind Gupta, Russell Impagliazzo |
| 1991 | Computing Sums of Radicals in Polynomial Time Johannes Blömer |
| 1991 | Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound Manfred Kunde |
| 1991 | Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM Donald B. Johnson, Panagiotis Takis Metaxas |
| 1991 | Discrepancy and epsilon-approximations for bounded VC-dimension Jirí Matousek, Emo Welzl, Lorenz Wernisch |
| 1991 | Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract) Baruch Awerbuch, George Varghese |
| 1991 | Dynamic Maintenance of Geometric Structures Made Easy Otfried Schwarzkopf |
| 1991 | Dynamic Scheduling on Parallel Machines Anja Feldmann, Jirí Sgall, Shang-Hua Teng |
| 1991 | Dynamic Three-Dimensional Linear Programming David Eppstein |
| 1991 | Efficient Algorithms for Dynamic Allocation of Distributed Memory Frank Thomson Leighton, Eric J. Schwabe |
| 1991 | Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve (Extended Abstract) Ming-Deh A. Huang, Doug Ierardi |
| 1991 | Efficient Exponentiation in Finite Fields (Extended Abstract) Joachim von zur Gathen |
| 1991 | Exact Learning of Read-Twice DNF Formulas (Extended Abstract) Howard Aizenstein, Leonard Pitt |
| 1991 | Explicit Construction of Natural Bounded Concentrators Moshe Morgenstern |
| 1991 | Fast Approximation Algorithms for Fractional Packing and Covering Problems Serge A. Plotkin, David B. Shmoys, Éva Tardos |
| 1991 | Faster Uniquely Represented Dictionaries Arne Andersson, Thomas Ottmann |
| 1991 | Fat Triangles Determine Linearly Many Holes Jirí Matousek, Nathaly Miller, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl |
| 1991 | Fault-tolerant Computation in the Full Information Model (Extended Abstract) Oded Goldreich, Shafi Goldwasser, Nathan Linial |
| 1991 | Finding k-cuts within Twice the Optimal Huzur Saran, Vijay V. Vazirani |
| 1991 | Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths David R. Karger, Daphne Koller, Steven J. Phillips |
| 1991 | Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract) Dror Lapidot, Adi Shamir |
| 1991 | Highly Fault-Tolerant Sorting Circuits Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton |
| 1991 | How to Learn an Unknown Environment (Extended Abstract) Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou |
| 1991 | How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing Peter W. Shor |
| 1991 | Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity Alon Orlitsky |
| 1991 | Languages that Are Easier than their Proofs Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser |
| 1991 | Low Contention Linearizable Counting Maurice Herlihy, Nir Shavit, Orli Waarts |
| 1991 | Lower Bounds for Data Structure Problems on RAMs (Extended Abstract) Amir M. Ben-Amram, Zvi Galil |
| 1991 | Lower Bounds for Polynomial Evaluation and Interpolation Problems Victor Shoup, Roman Smolensky |
| 1991 | Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates Anna Gál |
| 1991 | On ACC Richard Beigel, Jun Tarui |
| 1991 | On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract) Ding-Zhu Du, Yanjun Zhang, Qing Feng |
| 1991 | On Selecting a Satisfying Truth Assignment (Extended Abstract) Christos H. Papadimitriou |
| 1991 | On the Complexity of Computing the Homology Type of a Triangulation Bruce Randall Donald, Davied Renpan Chang |
| 1991 | On the Computational Power of Sigmoid versus Boolean Threshold Circuits Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag |
| 1991 | On the Exponent of the All Pairs Shortest Path Problem Noga Alon, Zvi Galil, Oded Margalit |
| 1991 | On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract) Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen |
| 1991 | On-line Scheduling in the Presence of Overload Sanjoy K. Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis E. Shasha |
| 1991 | Optimal File Sharing in Distributed Networks (Preliminary Version) Moni Naor, Ron M. Roth |
| 1991 | Optimal Prefetching via Data Compression (Extended Abstract) Jeffrey Scott Vitter, P. Krishnan |
| 1991 | Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices Ilan Adler, Peter A. Beling |
| 1991 | Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic Nils Klarlund |
| 1991 | Quantifying Knowledge Complexity Oded Goldreich, Erez Petrank |
| 1991 | Randomized Multidimensional Search Trees: Further Results in Dynamic Sampling (Extended Abstract) Ketan Mulmuley |
| 1991 | Randomized Multidimensional Search Trees: Lazy Balancing and Dynamic Shuffling (Extended Abstract) Ketan Mulmuley |
| 1991 | Reliable Computation with Noisy Circuits and Decision Trees-A General n log n Lower Bound Rüdiger Reischuk, Bernd Schmeltz |
| 1991 | Reporting Points in Halfspaces Jirí Matousek |
| 1991 | Scheduling Parallel Machines On-Line David B. Shmoys, Joel Wein, David P. Williamson |
| 1991 | Search Problems in the Decision Tree Model (Preliminary Version) László Lovász, Moni Naor, Ilan Newman, Avi Wigderson |
| 1991 | Self-Stabilization By Local Checking and Correction (Extended Abstract) Baruch Awerbuch, Boaz Patt-Shamir, George Varghese |
| 1991 | Shrinkage of de~Morgan formulae under restriction Mike Paterson, Uri Zwick |
| 1991 | Simulating BPP Using a General Weak Random Source David Zuckerman |
| 1991 | Size-Depth Tradeoffs for Algebraic Formulae Nader H. Bshouty, Richard Cleve, Wayne Eberly |
| 1991 | Subquadratic Zero-Knowledge Joan Boyar, Gilles Brassard, René Peralta |
| 1991 | The Art Gallery Theorem for Polygons With Holes Frank Hoffmann, Michael Kaufmann, Klaus Kriegel |
| 1991 | The Maintenance of Common Data in a Distributed System Baruch Awerbuch, Leonard J. Schulman |
| 1991 | Towards a Theory of Nearly Constant Time Parallel Algorithms Joseph Gil, Yossi Matias, Uzi Vishkin |
| 1991 | Tree Automata, Mu-Calculus and Determinacy (Extended Abstract) E. Allen Emerson, Charanjit S. Jutla |
| 1991 | Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version) Michael T. Goodrich |
| 1991 | Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fan-In Matthias Krause, Stephan Waack |
| 1991 | Walking an Unknown Street with Bounded Detour Rolf Klein |