| 1991 | Quantifying Knowledge Complexity | Oded Goldreich, Erez Petrank |
| 1991 | Fault-tolerant Computation in the Full Information Model (Extended Abstract) | Oded Goldreich, Shafi Goldwasser, Nathan Linial |
| 1991 | Towards a Theory of Nearly Constant Time Parallel Algorithms | Joseph Gil, Yossi Matias, Uzi Vishkin |
| 1991 | A Deterministic Parallel Algorithm for Planar Graphs Isomorphism | Hillel Gazit |
| 1991 | Efficient Exponentiation in Finite Fields (Extended Abstract) | Joachim von zur Gathen |
| 1991 | Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates | Anna Gl |
| 1991 | Applications of a Poset Representation to Edge Connectivity and Graph Rigidity | Harold N. Gabow |
| 1991 | Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees | Greg N. Frederickson |
| 1991 | Competitive Algorithms for Layered Graph Traversal | Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan |
| 1991 | Dynamic Scheduling on Parallel Machines | Anja Feldmann, Jir Sgall, Shang-Hua Teng |
| 1991 | Approximating Clique is Almost NP-Complete (Preliminary Version) | Uriel Feige, Shafi Goldwasser, Lszl Lovsz, Shmuel Safra, Mario Szegedy |
| 1991 | Amortized Communication Complexity (Preliminary Version) | Toms Feder, Eyal Kushilevitz, Moni Naor |
| 1991 | Dynamic Three-Dimensional Linear Programming | David Eppstein |
| 1991 | A General Approach to Removing Degeneracies | Ioannis Z. Emiris, John F. Canny |
| 1991 | Tree Automata, Mu-Calculus and Determinacy (Extended Abstract) | E. Allen Emerson, Charanjit S. Jutla |
| 1991 | Communication Complexity Towards Lower Bounds on Circuit Depth | Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jir Sgall |
| 1991 | A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract) | Herbert Edelsbrunner, Tiow Seng Tan |
| 1991 | On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract) | Ding-Zhu Du, Yanjun Zhang, Qing Feng |
| 1991 | On the Complexity of Computing the Homology Type of a Triangulation | Bruce Randall Donald, Davied Renpan Chang |
| 1991 | How to Learn an Unknown Environment (Extended Abstract) | Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou |
| 1991 | An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract) | Bernard Chazelle |
| 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 | Checking the Correctness of Memories | Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor |
| 1991 | Computing Sums of Radicals in Polynomial Time | Johannes Blmer |