| 1991 | Dynamic Trees and Dynamic Point Location (Preliminary Version) | Michael T. Goodrich, Roberto Tamassia |
| 1991 | Self-Testing/Correcting for Polynomials and for Approximate Functions | Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson |
| 1991 | Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract) | Zvi Galil, Giuseppe F. Italiano |
| 1991 | A Matroid Approach to Finding Edge Connectivity and Packing Arborescences | Harold N. Gabow |
| 1991 | Rigorous Time/Space Tradeoffs for Inverting Functions | Amos Fiat, Moni Naor |
| 1991 | Clique Partitions, Graph Compression, and Speeding-Up Algorithms | Toms Feder, Rajeev Motwani |
| 1991 | Non-Malleable Cryptography (Extended Abstract) | Danny Dolev, Cynthia Dwork, Moni Naor |
| 1991 | An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs | Hristo N. Djidjev, John H. Reif |
| 1991 | Infinite Games, Randomization, Computability, and Applications to Online Problems (Preliminary Version) | Xiaotie Deng, Sanjeev Mahajan |
| 1991 | Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract) | Edith Cohen, Nimrod Megiddo |
| 1991 | Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling | Edward G. Coffman Jr., M. R. Garey |
| 1991 | Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study | Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis |
| 1991 | Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract) | Joseph Cheriyan, Ramakrishna Thurimella |
| 1991 | Constructing Nonresidues in Finite Fields and the Extended Riemann Hypothesis | Johannes A. Buchmann, Victor Shoup |
| 1991 | Finding Hidden Hamiltonian Cycles (Extended Abstract) | Andrei Z. Broder, Alan M. Frieze, Eli Shamir |
| 1991 | Counting Linear Extensions is #P-Complete | Graham R. Brightwell, Peter Winkler |
| 1991 | A Lower Bound for Parallel String Matching | Dany Breslauer, Zvi Galil |
| 1991 | Competitive Paging with Locality of Reference (Preliminary Version) | Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber |
| 1991 | Navigating in Unfamiliar Geometric Terrain (Preliminary Version) | Avrim Blum, Prabhakar Raghavan, Baruch Schieber |
| 1991 | Linear Approximation of Shortest Superstrings | Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis |
| 1991 | PP Is Closed Under Intersection (Extended Abstract) | Richard Beigel, Nick Reingold, Daniel A. Spielman |
| 1991 | Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract) | Greg Barnes, Walter L. Ruzzo |
| 1991 | Checking Computations in Polylogarithmic Time | Lszl Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy |
| 1991 | Fast Monte Carlo Algorithms for Permutation Groups | Lszl Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, kos Seress |
| 1991 | Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups | Lszl Babai |