1997 Symposium on Theory of Computing

May 4-6, El Paso, Texas

List of accepted papers

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction, by Sanjeev Khanna, Madhu Sudan and David P. Williamson

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes, by S. Ben-David, N. Bshouty and E. Kushilevitz

A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria, by Aravind Srinivasan and Chung-Piaw Teo

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, by Miklos Ajtai and Cynthia Dwork

A polylog(n)-competitive algorithm for metrical task systems, by Yair Bartal, Avrim Blum, Carl Burch and Andrew Tomkins

A Sub-Constant Error-Probability Low-Degree test and a Sub-Constant Error-Probability PCP Characterization of NP by Ran Raz and Shmuel Safra

All of us are smarter than any of us: more on the robustness of the Consensus hierarchy, by Wai-Kau Lo and Vassos Hadzilacos

Allocating Bandwidth for Bursty Connections, by Jon Kleinberg, Yuval Rabani and Eva Tardos

An algorithm, unbiased for user impatience, for exact sampling via Markov chains, by James Fill

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point, by John H. Reif

Approximating Total Flow Time on Parallel Machines, by Stefano Leonardi and Danny Raz

Approximating hyper-rectangles: learning and pseudo-random sets, by Peter Auer, Philip M. Long and Aravind Srinivasan

Approximation algorithms for facility location problems, by Karen Aardal, David B. Shmoys and Eva Tardos

Approximation of k-Set Cover by Semi-Local Optimization, by Rong-chii Duh and Martin Furer

Better Bounds for Online Scheduling, by Susanne Albers

Byzantine Quorum Systems, by Dahlia Malkhi and Michael Reiter

Combinatorial Complexity of the Central Curve, by Peter A. Beling and Sushil Verma

Commodity-Based Cryptography, by Donald Beaver

Computationally Private Information Retrieval, by Benny Chor and Niv Gilboa

Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, by Tetsuo Asano, Naoki Katoh, Hisao Tamaki and Takeshi Tokuyama

Direct Product Results and the GCD Problem, in Old and New Communication Models, by I. Parnafes, R. Raz and A. Wigderson

Efficient Algorithms for Comparing Unrooted Evolutionary Trees by Ming-Yang Kao, Tak Wah Lam, Teresa Przytycka, Wing Kin Sung and Hing Fung Ting

Exploring Unknown Environments, by Susanne Albers and Monika Henzinger

Exponential Lower Bounds for Depth 3 Boolean Circuits, by Ramamohan Paturi, Michael E. Saks and Francis Zane

Fast and Precise Computations of Discrete Fourier Transforms using Cyclotomic Integers, by Joe Buhler, Amin Shokrollahi and Volker Stemann

Fault Tolerant Quantum Computation With Constant Error, by D. Aharonov and M. Ben-Or

Hamming Spaces, Euclid Spaces, and the Non-Approximability of Geometric TSP and MST, by Luca Trevisan

Improved Low Degree Testing and its Applications, by Sanjeev Arora and Madhu Sudan

Improved Pade approximation approach to decoding error-correcting codes, by Victor Y. Pan

Improved Routing and Sorting on Multibutterflies, by Bruce M. Maggs and Berthold Voecking

Incremental Clustering and Dynamic Information Retrieval, by Moses Charikar, Chandra Chekuri, Tomas Feder and Rajeev Motwani

Is $P \not = NC$ hard or unprovable? by Ketan Mulmuley

Linear Hashing Yields Small Buckets, by Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank and G\'abor Tardos

Linear Zero-Knowledge, by Ivan Damgaard and Ronald Cramer

Locality-Preserving Hashing in Multidimensional Spaces, by Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan and Santosh Vempala

Lower bounds for distributed coin-flipping and randomized consensus, by James Aspnes

Making Games Short, by Uri Feige and Joe Kilian

Nearest Neighbor Queries in Metric Spaces, by Kenneth L. Clarkson

Non-Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics, by J. Edmonds, D. Chinn, T. Brecht, and X. Deng

Oblivious Data Structures: Applications to Cryptography, by Daniele Micciancio

On ACC0[p^k] Frege proofs, by Alexis Maciel and Toniann Pitassi

On Approximately Counting Independent Sets, by Michael Luby and Eric Vigoda

On Floor Plan of Planar Graphs, by Xin He

On Sorting Strings in External Memory, by Lars Arge, Paolo Ferragina, Roberto Grossi and Jeffrey S. Vitter

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited, by Moni Naor and Omer Reingold

On-line Algorithms for Steiner Tree Problems, by Piotr Berman and Chris Coulston

Online Algorithms for Selective Multicast and Maximal Dense Trees, by Baruch Awerbuch and Tripurari Singh

Optimal time-critical scheduling via resource augmentation, by Cynthia Phillips, Cliff Stein, Eric Torng and Joel Wein

$P=BPP$ unless $E$ has sub-exponential circuits, by Russell Impagliazzo and Avi Wigderson

Page replacement with multi-size pages and applications to web caching, by Sandy Irani

Permanents, Pfaffian orientations, and even directed circuits, by William McCuaig, Neil Robertson, Paul Seymour and Robin Thomas

Pointer Jumping Requires Concurrent Read, by Noam Nisan and Ziv Bar-Yossef

Practical Erasure-Resilient Codes, by Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman and Volker Stemann

Private Information Storage, by Rafail Ostrovsky and Victor Shoup

Probabilistically Checkable Proofs with Zero Knowledge, by Joe Kilian, Erez Petrank and Gabor Tardos

Property Testing in Bounded Degree Graphs, by Oded Goldreich and Dana Ron

Quantum computation of Fourier transforms over symmetric groups, by Robert Beals

Randomized $\Omega (n^2)$ Lower Bound for Knapsack, by Dima Grigoriev and Marek Karpinski

Read-once branching programs, rectangular proofs of the pigeonhole principle, and the transversal calculus, by A. Razborov, A. Wigderson and A. Yao

Reducing Randomness via Irrational Numbers, by Zhi-Zhong Chen and Ming-Yang Kao

Reductions in Complexity Theory: An Isomorphism Theorem and a Gap Theorem, by Agrawal, Allender, Impagliazzo, Pitassi and Rudich

Relieving Hot Spots on the World Wide Web, by David Karger, Eric Lehman, Daniel Lewin, Matt Levine, Tom Leighton and Rina Panigrahy

Sampling Lattice Points, by Ravi Kannan and Santosh Vempala

$SL \subseteq L^{\frac{4}{3}}$, by Roy Armoni, Amnon Ta-Shma, Avi Wigderson and Shiyu Zhou

Some optimal inapproximability results, by Johan Hastad

Spectral Techniques for Expander Codes, by John Lafferty and Daniel Rockmore

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach, by Andrei Z. Broder, Alan M. Frieze and Eli Upfal

The Decidability of Distributed Decision Tasks, by Maurice Herlihy and Sergio Rajsbaum

The Linear-Array Problem in Communication Complexity Resolved, by Martin Dietzfelbinger

The Swendsen-Wang process does not always mix rapidly, by Vivek K. Gore and Mark R. Jerrum

Theory and applications of predictors that specialize, by Yoav Freund, Robert E. Schapire, Yoram Singer and Manfred K. Warmuth

Tree Pattern Matching and Subset Matching in Randomized O(n log^3n) Time, by Richard Cole and Ramesh Hariharan

Two Algorithms for Nearest-Neighbor Search in High Dimensions, by Jon M. Kleinberg

Universal O(congestion+dilation+\log^{1+\eps} N) local control packet switching algorithms, by Rafail Ostrovsky and Yuval Rabani

Using Random Sampling to Find Maximum Flows in Uncapacitated Graphs, by David Karger