| 1997 | Allocating Bandwidth for Bursty Connections. | Jon M. Kleinberg, Yuval Rabani, va Tardos |
| 1997 | Two Algorithms for Nearest-Neighbor Search in High Dimensions. | Jon M. Kleinberg |
| 1997 | Probabilistically Checkable Proofs with Zero Knowledge. | Joe Kilian, Erez Petrank, Gbor Tardos |
| 1997 | A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. | Sanjeev Khanna, Madhu Sudan, David P. Williamson |
| 1997 | Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. | David R. Karger, Eric P. Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin |
| 1997 | Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. | David R. Karger |
| 1997 | General Techniques for Comparing Unrooted Evolutionary Trees. | Ming-Yang Kao, Tak Wah Lam, Teresa M. Przytycka, Wing-Kin Sung, Hing-Fung Ting |
| 1997 | Sampling Lattice Points. | Ravi Kannan, Santosh S. Vempala |
| 1997 | Page Replacement with Multi-Size Pages and Applications to Web Caching. | Sandy Irani |
| 1997 | Locality-Preserving Hashing in Multidimensional Spaces. | Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh S. Vempala |
| 1997 | Untitled record | Russell Impagliazzo, Avi Wigderson |
| 1997 | The Decidability of Distributed Decision Tasks (Extended Abstract). | Maurice Herlihy, Sergio Rajsbaum |
| 1997 | On Floorplans of Planar Graphs. | Xin He |
| 1997 | Some Optimal Inapproximability Results. | Johan Hstad |
| 1997 | Randomized Omega(n | Dima Grigoriev, Marek Karpinski |
| 1997 | The Swendsen-Wang Process Does Not Always Mix Rapidly. | Vivek Gore, Mark Jerrum |
| 1997 | Property Testing in Bounded Degree Graphs. | Oded Goldreich, Dana Ron |
| 1997 | Using and Combining Predictors That Specialize. | Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth |
| 1997 | Retraction of Probabilistic Computation and Linear Time. | Lance Fortnow, Michael Sipser |
| 1997 | An Interruptible Algorithm for Perfect Sampling via Markov Chains. | James Allen Fill |
| 1997 | Making Games Short (Extended Abstract). | Uriel Feige, Joe Kilian |
| 1997 | Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). | Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng |
| 1997 | Approximation of | Rong-chii Duh, Martin Frer |
| 1997 | The Linear-Array Problem in Communication Complexity Resolved. | Martin Dietzfelbinger |
| 1997 | Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. | Ronald Cramer, Ivan Damgrd |