| 1991 | A General Completeness Theorem for Two-Party Games Joe Kilian |
| 1991 | A Lower Bound for Parallel String Matching Dany Breslauer, Zvi Galil |
| 1991 | A Matroid Approach to Finding Edge Connectivity and Packing Arborescences Harold N. Gabow |
| 1991 | A Model for Data in Motion Simon Kahan |
| 1991 | Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract) Joseph Cheriyan, Ramakrishna Thurimella |
| 1991 | An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs Hristo N. Djidjev, John H. Reif |
| 1991 | Approximations and Optimal Geometric Divide-And-Conquer Jirí Matousek |
| 1991 | Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer |
| 1991 | Checking Computations in Polylogarithmic Time László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy |
| 1991 | Clique Partitions, Graph Compression, and Speeding-Up Algorithms Tomás Feder, Rajeev Motwani |
| 1991 | Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing (Extended Abstract) Zvi M. Kedem, Krishna V. Palem, A. Raghunathan, Paul G. Spirakis |
| 1991 | Competitive Paging with Locality of Reference (Preliminary Version) Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber |
| 1991 | Constant-Time Parallel Integer Sorting (Extended Abstract) Torben Hagerup |
| 1991 | Constructing Nonresidues in Finite Fields and the Extended Riemann Hypothesis Johannes A. Buchmann, Victor Shoup |
| 1991 | Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (Extended Abstract) Yossi Matias, Uzi Vishkin |
| 1991 | Counting Linear Extensions is #P-Complete Graham R. Brightwell, Peter Winkler |
| 1991 | Counting Networks and Multi-Processor Coordination James Aspnes, Maurice Herlihy, Nir Shavit |
| 1991 | Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract) Greg Barnes, Walter L. Ruzzo |
| 1991 | Dynamic Trees and Dynamic Point Location (Preliminary Version) Michael T. Goodrich, Roberto Tamassia |
| 1991 | Effective Noether Irreducibility Forms and Applications (Extended Abstract) Erich L. Kaltofen |
| 1991 | Factoring Numbers Using Singular Integers Leonard M. Adleman |
| 1991 | Fast Approximation Algorithms for Multicommodity Flow Problems Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas |
| 1991 | Fast Monte Carlo Algorithms for Permutation Groups László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress |
| 1991 | Finding Hidden Hamiltonian Cycles (Extended Abstract) Andrei Z. Broder, Alan M. Frieze, Eli Shamir |
| 1991 | Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract) Zvi Galil, Giuseppe F. Italiano |
| 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 | Generic Computation and Its Complexity Serge Abiteboul, Victor Vianu |
| 1991 | Hamiltonian Paths in Infinite Graphs David Harel |
| 1991 | Hidden Surface Removal with Respect to a Moving View Point Ketan Mulmuley |
| 1991 | Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract) Edith Cohen, Nimrod Megiddo |
| 1991 | Infinite Games, Randomization, Computability, and Applications to Online Problems (Preliminary Version) Xiaotie Deng, Sanjeev Mahajan |
| 1991 | Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (Extended Abstract) Ker-I Ko |
| 1991 | Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract) Eyal Kushilevitz, Yishay Mansour |
| 1991 | Linear Approximation of Shortest Superstrings Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis |
| 1991 | Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups László Babai |
| 1991 | Lower Bounds for Non-Commutative Computation (Extended Abstract) Noam Nisan |
| 1991 | Lower Bounds for Randomized k-Server and Motion Planning Algorithms Howard J. Karloff, Yuval Rabani, Yiftach Ravid |
| 1991 | Navigating in Unfamiliar Geometric Terrain (Preliminary Version) Avrim Blum, Prabhakar Raghavan, Baruch Schieber |
| 1991 | Non-Malleable Cryptography (Extended Abstract) Danny Dolev, Cynthia Dwork, Moni Naor |
| 1991 | On Deterministic Approximation of DNF Michael Luby, Boban Velickovic |
| 1991 | On-Line Learning of Linear Functions Nick Littlestone, Philip M. Long, Manfred K. Warmuth |
| 1991 | PP Is Closed Under Intersection (Extended Abstract) Richard Beigel, Nick Reingold, Daniel A. Spielman |
| 1991 | Perfect Cryptographic Security from Partially Independent Channels Ueli M. Maurer |
| 1991 | Probabilistic Recurrence Relations Richard M. Karp |
| 1991 | Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA Cris Koutsougeras, Jeffrey Scott Vitter |
| 1991 | Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling Edward G. Coffman Jr., M. R. Garey |
| 1991 | Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field Alfred Menezes, Scott A. Vanstone, Tatsuaki Okamoto |
| 1991 | Rigorous Time/Space Tradeoffs for Inverting Functions Amos Fiat, Moni Naor |
| 1991 | Rounds in Communication Complexity Revisited Noam Nisan, Avi Wigderson |
| 1991 | Sampling and Integration of Near Log-Concave functions David L. Applegate, Ravi Kannan |
| 1991 | Searching in the Presence of Linearly Bounded Errors (Extended Abstract) Javed A. Aslam, Aditi Dhagat |
| 1991 | Self-Testing/Correcting for Polynomials and for Approximate Functions Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson |
| 1991 | Separating Concurrent Languages with Categories of Language Embeddings (Extended Abstract) Ehud Shapiro |
| 1991 | Testing Finite State Machines (Extended Abstract) Mihalis Yannakakis, David Lee |
| 1991 | The Expressive Power of Voting Polynomials James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich |
| 1991 | The Harmonic Online K-Server Algorithm Is Competitive Edward F. Grove |
| 1991 | Wait-free Parallel Algorithms for the Union-Find Problem Richard J. Anderson, Heather Woll |
| 1991 | When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks Ajit Agrawal, Philip N. Klein, R. Ravi |
| 1991 | When Won't Membership Queries Help? (Extended Abstract) Dana Angluin, Michael Kharitonov |