| 1991 | A Unified Geometric Approach to Graph Separators | Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis |
| 1991 | Discrepancy and epsilon-approximations for bounded VC-dimension | Jir Matousek, Emo Welzl, Lorenz Wernisch |
| 1991 | Fat Triangles Determine Linearly Many Holes | Jir Matousek, Nathaly Miller, Jnos Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl |
| 1991 | Reporting Points in Halfspaces | Jir Matousek |
| 1991 | On the Computational Power of Sigmoid versus Boolean Threshold Circuits | Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag |
| 1991 | Search Problems in the Decision Tree Model (Preliminary Version) | Lszl Lovsz, Moni Naor, Ilan Newman, Avi Wigderson |
| 1991 | Efficient Algorithms for Dynamic Allocation of Distributed Memory | Frank Thomson Leighton, Eric J. Schwabe |
| 1991 | Highly Fault-Tolerant Sorting Circuits | Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton |
| 1991 | Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract) | Dror Lapidot, Adi Shamir |
| 1991 | Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound | Manfred Kunde |
| 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 |
| 1991 | Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic | Nils Klarlund |
| 1991 | Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths | David R. Karger, Daphne Koller, Steven J. Phillips |
| 1991 | A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) | Bruce M. Kapron, Stephen A. Cook |
| 1991 | On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract) | Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen |
| 1991 | Better Expansion for Ramanujan Graphs | Nabil Kahal |
| 1991 | Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM | Donald B. Johnson, Panagiotis Takis Metaxas |
| 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 | A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract) | Tsan-sheng Hsu, Vijaya Ramachandran |
| 1991 | The Art Gallery Theorem for Polygons With Holes | Frank Hoffmann, Michael Kaufmann, Klaus Kriegel |
| 1991 | Low Contention Linearizable Counting | Maurice Herlihy, Nir Shavit, Orli Waarts |
| 1991 | Computing Planar Intertwines | Arvind Gupta, Russell Impagliazzo |
| 1991 | An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] | Dima Grigoriev, Marek Karpinski |
| 1991 | Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version) | Michael T. Goodrich |