| 1997 | When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). | Luca Trevisan |
| 1997 | A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria. | Aravind Srinivasan, Chung-Piaw Teo |
| 1997 | Approximation Algorithms for Facility Location Problems (Extended Abstract). | David B. Shmoys, va Tardos, Karen I. Aardal |
| 1997 | Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. | John H. Reif |
| 1997 | A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. | Ran Raz, Shmuel Safra |
| 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 | Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). | Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein |
| 1997 | Exponential Lower Bounds for Depth 3 Boolean Circuits. | Ramamohan Paturi, Michael E. Saks, Francis Zane |
| 1997 | Direct Product Results and the GCD Problem, in Old and New Communication Models. | Itzhak Parnafes, Ran Raz, Avi Wigderson |
| 1997 | Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. | Victor Y. Pan |
| 1997 | Private Information Storage (Extended Abstract). | Rafail Ostrovsky, Victor Shoup |
| 1997 | Universal | Rafail Ostrovsky, Yuval Rabani |
| 1997 | Pointer Jumping Requires Concurrent Read. | Noam Nisan, Ziv Bar-Yossef |
| 1997 | On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). | Moni Naor, Omer Reingold |
| 1997 | Is There an Algebraic Proof for | Ketan Mulmuley |
| 1997 | Oblivious Data Structures: Applications to Cryptography. | Daniele Micciancio |
| 1997 | Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). | William McCuaig, Neil Robertson, Paul D. Seymour, Robin Thomas |
| 1997 | Byzantine Quorum Systems. | Dahlia Malkhi, Michael K. Reiter |
| 1997 | Improved Routing and Sorting on Multibutterflies. | Bruce M. Maggs, Berthold Vcking |
| 1997 | On ACC | Alexis Maciel, Toniann Pitassi |
| 1997 | Approximately Counting Up To Four (Extended Abstract). | Michael Luby, Eric Vigoda |
| 1997 | Practical Loss-Resilient Codes. | Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, Volker Stemann |
| 1997 | All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. | Wai-Kau Lo, Vassos Hadzilacos |
| 1997 | Approximating Total Flow Time on Parallel Machines. | Stefano Leonardi, Danny Raz |
| 1997 | Spectral Techniques for Expander Codes. | John D. Lafferty, Daniel N. Rockmore |