| 1997 | Tree Pattern Matching and Subset Matching in Randomized O(n log | Richard Cole, Ramesh Hariharan |
| 1997 | Nearest Neighbor Queries in Metric Spaces. | Kenneth L. Clarkson |
| 1997 | Eigenvalues, Flows and Separators of Graphs. | Fan R. K. Chung, Shing-Tung Yau |
| 1997 | Computationally Private Information Retrieval (Extended Abstract). | Benny Chor, Niv Gilboa |
| 1997 | Reducing Randomness via Irrational Numbers. | Zhi-Zhong Chen, Ming-Yang Kao |
| 1997 | Incremental Clustering and Dynamic Information Retrieval. | Moses Charikar, Chandra Chekuri, Toms Feder, Rajeev Motwani |
| 1997 | Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. | Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann |
| 1997 | Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). | Andrei Z. Broder, Alan M. Frieze, Eli Upfal |
| 1997 | On-Line Algorithms for Steiner Tree Problems (Extended Abstract). | Piotr Berman, Chris Coulston |
| 1997 | A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. | Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz |
| 1997 | Combinatorial Complexity of the Central Curve. | Peter A. Beling, Sushil Verma |
| 1997 | Commodity-Based Cryptography (Extended Abstract). | Donald Beaver |
| 1997 | Quantum Computation of Fourier Transforms over Symmetric Groups. | Robert Beals |
| 1997 | A polylog( | Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins |
| 1997 | Paul Erds (1913-1996): His Influence on the Theory of Computing. | Lszl Babai |
| 1997 | Online Algorithms for Selective Multicast and Maximal Dense Trees. | Baruch Awerbuch, Tripurari Singh |
| 1997 | Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets. | Peter Auer, Philip M. Long, Aravind Srinivasan |
| 1997 | Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. | James Aspnes |
| 1997 | Covering Points in the Plane by | Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama |
| 1997 | Improved Low-Degree Testing and its Applications. | Sanjeev Arora, Madhu Sudan |
| 1997 | SL <= L | Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou |
| 1997 | On Sorting Strings in External Memory (Extended Abstract). | Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter |
| 1997 | Is Linear Hashing Good? | Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gbor Tardos |
| 1997 | Exploring Unknown Environments. | Susanne Albers, Monika Rauch Henzinger |
| 1997 | Better Bounds for Online Scheduling. | Susanne Albers |