| 1997 | A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Sanjeev Khanna, Madhu Sudan, David P. Williamson |
| 1997 | A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz |
| 1997 | A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria. Aravind Srinivasan, Chung-Piaw Teo |
| 1997 | A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. Miklós Ajtai, Cynthia Dwork |
| 1997 | A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. Ran Raz, Shmuel Safra |
| 1997 | A polylog( Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins |
| 1997 | Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. Alexander Vardy |
| 1997 | All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. Wai-Kau Lo, Vassos Hadzilacos |
| 1997 | Allocating Bandwidth for Bursty Connections. Jon M. Kleinberg, Yuval Rabani, Éva Tardos |
| 1997 | An Interruptible Algorithm for Perfect Sampling via Markov Chains. James Allen Fill |
| 1997 | Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. John H. Reif |
| 1997 | Approximately Counting Up To Four (Extended Abstract). Michael Luby, Eric Vigoda |
| 1997 | Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets. Peter Auer, Philip M. Long, Aravind Srinivasan |
| 1997 | Approximating Total Flow Time on Parallel Machines. Stefano Leonardi, Danny Raz |
| 1997 | Approximation Algorithms for Facility Location Problems (Extended Abstract). David B. Shmoys, Éva Tardos, Karen I. Aardal |
| 1997 | Approximation of Rong-chii Duh, Martin Fürer |
| 1997 | Better Bounds for Online Scheduling. Susanne Albers |
| 1997 | Byzantine Quorum Systems. Dahlia Malkhi, Michael K. Reiter |
| 1997 | Combinatorial Complexity of the Central Curve. Peter A. Beling, Sushil Verma |
| 1997 | Commodity-Based Cryptography (Extended Abstract). Donald Beaver |
| 1997 | Computationally Private Information Retrieval (Extended Abstract). Benny Chor, Niv Gilboa |
| 1997 | Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin |
| 1997 | Covering Points in the Plane by Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama |
| 1997 | Direct Product Results and the GCD Problem, in Old and New Communication Models. Itzhak Parnafes, Ran Raz, Avi Wigderson |
| 1997 | Eigenvalues, Flows and Separators of Graphs. Fan R. K. Chung, Shing-Tung Yau |
| 1997 | Exploring Unknown Environments. Susanne Albers, Monika Rauch Henzinger |
| 1997 | Exponential Lower Bounds for Depth 3 Boolean Circuits. Ramamohan Paturi, Michael E. Saks, Francis Zane |
| 1997 | Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann |
| 1997 | Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. Victor Y. Pan |
| 1997 | Fault-Tolerant Quantum Computation With Constant Error. Dorit Aharonov, Michael Ben-Or |
| 1997 | General Techniques for Comparing Unrooted Evolutionary Trees. Ming-Yang Kao, Tak Wah Lam, Teresa M. Przytycka, Wing-Kin Sung, Hing-Fung Ting |
| 1997 | Improved Low-Degree Testing and its Applications. Sanjeev Arora, Madhu Sudan |
| 1997 | Improved Routing and Sorting on Multibutterflies. Bruce M. Maggs, Berthold Vöcking |
| 1997 | Incremental Clustering and Dynamic Information Retrieval. Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani |
| 1997 | Is Linear Hashing Good? Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos |
| 1997 | Is There an Algebraic Proof for Ketan Mulmuley |
| 1997 | Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. Ronald Cramer, Ivan Damgård |
| 1997 | Locality-Preserving Hashing in Multidimensional Spaces. Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh S. Vempala |
| 1997 | Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. James Aspnes |
| 1997 | Making Games Short (Extended Abstract). Uriel Feige, Joe Kilian |
| 1997 | Nearest Neighbor Queries in Metric Spaces. Kenneth L. Clarkson |
| 1997 | Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng |
| 1997 | Oblivious Data Structures: Applications to Cryptography. Daniele Micciancio |
| 1997 | On ACC Alexis Maciel, Toniann Pitassi |
| 1997 | On Floorplans of Planar Graphs. Xin He |
| 1997 | On Sorting Strings in External Memory (Extended Abstract). Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter |
| 1997 | On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). Moni Naor, Omer Reingold |
| 1997 | On-Line Algorithms for Steiner Tree Problems (Extended Abstract). Piotr Berman, Chris Coulston |
| 1997 | Online Algorithms for Selective Multicast and Maximal Dense Trees. Baruch Awerbuch, Tripurari Singh |
| 1997 | Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein |
| 1997 | Page Replacement with Multi-Size Pages and Applications to Web Caching. Sandy Irani |
| 1997 | Paul Erdös (1913-1996): His Influence on the Theory of Computing. László Babai |
| 1997 | Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). William McCuaig, Neil Robertson, Paul D. Seymour, Robin Thomas |
| 1997 | Pointer Jumping Requires Concurrent Read. Noam Nisan, Ziv Bar-Yossef |
| 1997 | Practical Loss-Resilient Codes. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, Volker Stemann |
| 1997 | Private Information Storage (Extended Abstract). Rafail Ostrovsky, Victor Shoup |
| 1997 | Probabilistically Checkable Proofs with Zero Knowledge. Joe Kilian, Erez Petrank, Gábor Tardos |
| 1997 | Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997 Frank Thomson Leighton, Peter W. Shor |
| 1997 | Property Testing in Bounded Degree Graphs. Oded Goldreich, Dana Ron |
| 1997 | Quantum Computation of Fourier Transforms over Symmetric Groups. Robert Beals |
| 1997 | Randomized Omega(n Dima Grigoriev, Marek Karpinski |
| 1997 | Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao |
| 1997 | Reducing Randomness via Irrational Numbers. Zhi-Zhong Chen, Ming-Yang Kao |
| 1997 | Reducing the Complexity of Reductions. Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich |
| 1997 | Retraction of Probabilistic Computation and Linear Time. Lance Fortnow, Michael Sipser |
| 1997 | SL <= L Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou |
| 1997 | Sampling Lattice Points. Ravi Kannan, Santosh S. Vempala |
| 1997 | Some Optimal Inapproximability Results. Johan Håstad |
| 1997 | Spectral Techniques for Expander Codes. John D. Lafferty, Daniel N. Rockmore |
| 1997 | Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1997 | The Decidability of Distributed Decision Tasks (Extended Abstract). Maurice Herlihy, Sergio Rajsbaum |
| 1997 | The Linear-Array Problem in Communication Complexity Resolved. Martin Dietzfelbinger |
| 1997 | The Swendsen-Wang Process Does Not Always Mix Rapidly. Vivek Gore, Mark Jerrum |
| 1997 | Tree Pattern Matching and Subset Matching in Randomized O(n log Richard Cole, Ramesh Hariharan |
| 1997 | Two Algorithms for Nearest-Neighbor Search in High Dimensions. Jon M. Kleinberg |
| 1997 | Universal Rafail Ostrovsky, Yuval Rabani |
| 1997 | Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. David R. Karger |
| 1997 | Using and Combining Predictors That Specialize. Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth |
| 1997 | When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). Luca Trevisan |