| 1997 | 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19-22, 1997 |
| 1997 | A 2-Approximation Algorithm for the Directed Multiway Cut Problem. Joseph Naor, Leonid Zosin |
| 1997 | A 7/8-Approximation Algorithm for MAX 3SAT? Howard J. Karloff, Uri Zwick |
| 1997 | A Complete Promise Problem for Statistical Zero-Knowledge. Amit Sahai, Salil P. Vadhan |
| 1997 | A Concrete Security Treatment of Symmetric Encryption. Mihir Bellare, Anand Desai, E. Jokipii, Phillip Rogaway |
| 1997 | A Faster Deterministic Algorithm for Minimum Spanning Trees. Bernard Chazelle |
| 1997 | A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. Santosh S. Vempala |
| 1997 | Alternating-time Temporal Logic. Rajeev Alur, Thomas A. Henzinger, Orna Kupferman |
| 1997 | An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. Saugata Basu |
| 1997 | An Improved Worst-Case to Average-Case Connection for Lattice Problems. Jin-Yi Cai, Ajay Nerurkar |
| 1997 | Approximating Shortest Paths on an Nonconvex Polyhedron. Kasturi R. Varadarajan, Pankaj K. Agarwal |
| 1997 | Beyond the Flow Decomposition Barrier. Andrew V. Goldberg, Satish Rao |
| 1997 | Buy-at-Bulk Network Design. Baruch Awerbuch, Yossi Azar |
| 1997 | Computable Obstructions to Wait-free Computability. John Havlicek |
| 1997 | Computing Integral Points in Convex Semi-algebraic Sets. Leonid Khachiyan, Lorant Porkolab |
| 1997 | Constant Depth Circuits and the Lutz Hypothesis. Jin-Yi Cai, D. Sivakumar, Martin Strauss |
| 1997 | Contention Resolution with Guaranteed Constant Expected Delay. Leslie Ann Goldberg, Philip D. MacKenzie |
| 1997 | Deciding Properties of Polynomials Without Factoring. Tomas Sander, Mohammad Amin Shokrollahi |
| 1997 | Deterministic Superimposed Coding with Applications to Pattern Matching. Piotr Indyk |
| 1997 | Does Parallel Repetition Lower the Error in Computationally Sound Protocols? Mihir Bellare, Russell Impagliazzo, Moni Naor |
| 1997 | Edge-Connectivity Augmentation Preserving Simplicity. Jørgen Bang-Jensen, Tibor Jordán |
| 1997 | Exploiting Locality for Data Management in Systems of Limited Bandwidth. Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann |
| 1997 | Finding an Even Hole in a Graph. Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vuskovic |
| 1997 | Flows in Undirected Unit Capacity Networks. Andrew V. Goldberg, Satish Rao |
| 1997 | General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang |
| 1997 | Global Optimization Using Local Information with Applications to Flow Control. Yair Bartal, John W. Byers, Danny Raz |
| 1997 | Hamiltonian Cycles in Solid Grid Graphs. Christopher Umans, William J. Lenhart |
| 1997 | Improved Approximation Algorithms for Unsplittable Flow Problems. Stavros G. Kolliopoulos, Clifford Stein |
| 1997 | Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. Aravind Srinivasan |
| 1997 | Improved Approximations for Shallow-Light Spanning Trees. Joseph Naor, Baruch Schieber |
| 1997 | Improved Bounds on Planar k-sets and k-levels. Tamal K. Dey |
| 1997 | Learning Noisy Perceptrons by a Perceptron in Polynomial Time. Edith Cohen |
| 1997 | Lower Bounds for the Signature Size of Incremental Schemes. Marc Fischlin |
| 1997 | Making Nondeterminism Unambiguous. Klaus Reinhardt, Eric Allender |
| 1997 | Minimizing Flow Time Nonclairvoyantly. Bala Kalyanasundaram, Kirk Pruhs |
| 1997 | Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. Sanjeev Arora |
| 1997 | Nearly Tight Bounds on the Learnability of Evolution. Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan |
| 1997 | New Directions in Cryptography: Twenty Some Years Later. Shafi Goldwasser |
| 1997 | No Feasible Interpolation for TC0-Frege Proofs. Maria Luisa Bonet, Toniann Pitassi, Ran Raz |
| 1997 | Number-theoretic Constructions of Efficient Pseudo-random Functions. Moni Naor, Omer Reingold |
| 1997 | On the Complexity of a Set-Union Problem. Richard J. Lipton, Paul J. Martino, Andy Neitzke |
| 1997 | On the Power of Quantum Finite State Automata. Attila Kondacs, John Watrous |
| 1997 | Optimal Resilience Proactive Public-Key Cryptosystems. Yair Frankel, Peter Gemmell, Philip D. MacKenzie, Moti Yung |
| 1997 | Optimal Suffix Tree Construction with Large Alphabets. Martin Farach |
| 1997 | Parallelizing Elimination Orders with Linear Fill. Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi |
| 1997 | Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. Russ Bubley, Martin E. Dyer |
| 1997 | Pattern Matching with Swaps. Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein |
| 1997 | Randomized Allocation Processes. Artur Czumaj, Volker Stemann |
| 1997 | Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. Pascal Koiran |
| 1997 | Reliable Cellular Automata with Self-Organization. Péter Gács |
| 1997 | Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. Eyal Kushilevitz, Rafail Ostrovsky |
| 1997 | Satisfiability Coding Lemma. Ramamohan Paturi, Pavel Pudlák, Francis Zane |
| 1997 | Separation of the Monotone NC Hierarchy. Ran Raz, Pierre McKenzie |
| 1997 | Storage Management for Evolving Databases. Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, Suresh Venkatasubramanian |
| 1997 | Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. J. Ian Munro, Venkatesh Raman |
| 1997 | The Analysis of a List-Coloring Algorithm on a Random Graph. Dimitris Achlioptas, Michael S. O. Molloy |
| 1997 | The Competitive Analysis of Risk Taking with Applications to Online Trading. Sabah al-Binali |
| 1997 | The Computational Complexity of Knot and Link Problems. Joel Hass, J. C. Lagarias, Nicholas Pippenger |
| 1997 | The Minimization Problem for Boolean Formulas. Edith Hemaspaandra, Gerd Wechsung |
| 1997 | Tight Bounds for Depth-two Superconcentrators. Jaikumar Radhakrishnan, Amnon Ta-Shma |
| 1997 | Truly Online Paging with Locality of Reference. Amos Fiat, Manor Mendel |
| 1997 | Two Decades of Temporal Logic: Achievements and Challenges (Abstract). Amir Pnueli |
| 1997 | Undirected Single Source Shortest Path in Linear Time. Mikkel Thorup |
| 1997 | Weak Random Sources, Hitting Sets, and BPP Simulations. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan |