STOC2002 Accepted Papers


Quantum Lower Bound for the Collision Problem

Scott Aaronson


Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai and Abhi Shelat


Near-Optimal Sparse Fourier Representations via Sampling

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan and Martin J. Strauss


Combinatorial Optimization Problems in Self-Assembly

Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo M. de Moisset and Paul W. K. Rothemund


The Invasiveness of Off-line Memory Checking

Miklos Ajtai


Crawling on Web Graphs

Colin Cooper and Alan Frieze


Optimal Rate-based Scheduling on Multiprocessors

Anand Srinivasan and James H. Anderson


Space-Efficient Approximate Voronoi Diagrams

Sunil Arya, Theocharis Malamatos and David M. Mount


Secure Multi-party Quantum Computing

Claude Crepeau, Daniel Gottesman and Adam Smith


Wait-Free Consensus with Infinite Arrivals

James Aspnes, Gauri Shah and Jatin Shah


Approximation Algorithms for Minimum-Cost k-Vertex Connected Subgraphs

Joseph Cheriyan, Santosh Vempala and Adrian Vetta


Expanders from Symmetric Codes

Roy Meshulam and Avi Wigderson


Girth and Euclidean Distortion

Nathan Linial, Avner Magen and Assaf Naor


The Complexity of Approximating the Entropy

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar and Ronitt Rubinfeld


Strict Polynomial-time in Simulation and Extraction

Boaz Barak and Yehuda Lindell


Universally Composable Two-party Computation

Ran Canetti and Yehuda Lindell, , Rafail Ostrovsky and Amit Sahai


Remier's Inequality and Tardos' Conjecture

Clifford Smyth


Selfish Traffic Allocation for Server Farms

Artur Czumaj, Piotr Krysta and Berthold Voecking


Improved Cryptographic Hash Functions with Worst-case/Average-case Connection

Daniele Micciancio


On the Complexity of Equilibria

Xiaotie Deng, Christos Papadimitriou and Shmuel Safra


Tight Security Proofs for the Bounded-Storage Model

Stefan Dziembowski and Ueli Maurer


Average Case Analysis for Batched Disk Scheduling and Increasing Sequences



New Results on Monotone Dualization and Generating Hypergraph Transversals

Thomas Eiter, Georg Gottlob and Kazuhisa Makino


Size Space Tradeoffs for Resolution

Eli Ben-Sasson


Hard Examples for Bounded Depth Frege

Eli Ben-Sasson


Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem

Michael Elkin and Guy Kortsarz


Time-Space Tradeoffs Multiparty Communication Complexity and Nearest Neighbor Problems

Paul Beame and Erik Vee


Relations between Average Case Complexity and Approximation Complexity

Uriel Feige


Clairvoyant Scheduling of Random Walks

Peter Gacs


Meldable Heaps and Boolean Union-Find

Haim Kaplan, Nira Shafrir and Robert E. Tarjan


Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem

Sean Hallgren


Deterministic Sorting in O(nloglogn) Time and Linear Space

Yijie Han



Ian Agol Joel Hass William P. Thurston


Exact learning of DNF formulas using DNF hypotheses

Lisa Hellerstein and Vijay Raghavan


The Importance of Being Biased

Irit Dinur and Shmuel Safra


An Exponential Separation between Regular and General Resolution

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi and Alasdair Urquhart


Competitive Recommendation Systems

Petros Drineas, Iordanis Kerenidis and Prabhakar Raghavan


Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon

Jonas Holmerin


Competitive Generalized Auctions

Amos Fiat, Andrew V. Goldberg, Jason D. Hartline and Anna R. Karlin


Load Balancing in Dynamic Adversarial Systems

Elliot Anshelevich, David Kempe and Jon Kleinberg


Fitting Algebraic Curves to Noisy Data

Sanjeev Arora Subhash Khot


Hardness Results for Approximate Hypergraph Coloring

Subhash Khot


On the Power of Unique 2-Prover 1-Round Games

Subhash Khot


Equitable Truth-Revealing Cost Allocations via Primal-Dual-Type

Kamal Jain and Vijay Vazirani


Cache-Oblivious Priority Queue and Graph Algorithm Applications

Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley and J. Ian Munro


On Paging with Locality of Reference

Susanne Albers, Lene M. Favrholdt and Oliver Giel


A New Greedy Approach for Facility Location Problems

Kamal Jain, Mohammad Mahdian and Amin Saberi


Random Sampling and Approximation of MAX-CSP Problems

Noga Alon,  W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski


A Polynomial Time Algorithm to Approximately Count Contingency

Mary Cryan and Martin Dyer


Tradeoffs in Probabilistic Packet Marking for IP Traceback

Micah Adler


Models and Thresholds for Random Constraint Satisfaction Problems

Michael Molloy


The Glauber Dynamics on the Colourings of a Graph with High Girth and Maximum Degree

Michael Molloy


Almost All Graphs with Average Degree 4 are 3-Colorable

Dimitris Achlioptas and Cristopher Moore


Similarity Estimation Techniques from Rounding Algorithms

Moses Charikar


Recognizing String Graphs in NP

Marcus Schaefer, Eric Sedgwick and Daniel Stefankovic


Random Sampling in Residual Graphs

David R. Karger and Matthew S.  Levine


On Communication over an Entanglement-Assisted Quantum Channel

Ashwin Nayak and Julia Salzman


Huffman Coding with Unequal Letter Costs

Mordecai J. Golin Claire Kenyon Neal E. Young


Concurrent Zero-Knowledge With Timing Revisited

Oded Goldreich


Hardness Amplification Within NP

Ryan O'Donnell


Randomness Conductors and Constant-Degree Lossless Expanders

Michael Capalbo, Omer Reingold, Salil Vadhan and Avi Wigderson


Verifying Candidate Matches in Sparse and Wildcard Matching

Richard Cole and Ramesh Hariharan


Resolution Lower Bounds for the Weak Pigeon Hole Principle

Ran Raz


On the Complexity of Matrix Product

Ran Raz


Learnability Beyond AC0

Jeffrey C. Jackson, Adam R. Klivans and Rocco A. Servedio


Finding Nearest Neighbors in Growth-restricted Metrics

David Karger and Matthias Ruhl


On Randomized Online Scheduling

Susanne Albers


Approximation Schemes for Preemptive Weighted Flow Time

Chandra Chekuri and Sanjeev Khanna


Approximate Clustering via Core-Sets

Mihai Badoiu, Sariel Har-Peled and Piotr Indyk


Computing the Betti Numbers of Arrangements

Saugata Basu


A New average Case Analysis for Completion Time Scheduling

Mark Scharbrodt, Thomas Schickinger and Angelika Steger


Clifford algebras and Approximating the Permanent

Steve Chien, Lars Rasmussen and Alistair Sinclair


Approximate Counting of Inversions in a Data Stream

Miklos Ajtai, T.S. Jayram, Ravi Kumar and D. Sivakumar


Algorithmic derandomization via Complexity Theory

D. Sivakumar


The Complexity of Choosing an H-Colouring (Nearly) Uniformly at Random

Leslie Ann Goldberg, Steven Kelk and Mike Paterson


Monotonicity Testing over General Poset Domains

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky


Lower Bounds and Competitive Algorithms for On-Line Scheduling of Unit-Size Tasks to Related Machines

Spyros Kontogiannis


Improved Decremental Algorithms for Transitive Closure and All-pairs Shortest Paths

Surender Baswana, Ramesh Hariharan and Sandeep Sen


2-Round Zero Knowledge and Proof Auditors

Cynthia Dwork and Larry Stockmeyer


Fast Small-space Algorithms for Approximate Histogram Maintenance

Anna Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan and Martin J. Strauss


Space Lower Bounds for Distance Approximation in the Data Stream Model

Michael Saks and Xiaodong Sun


On the Composition of Authenticated Byzantine Agreement

Ydhuda Lindell, Anna Lysyanskaya and Tal Rabin


The Price of Anarchy is Independent of the Network Topology

Tim Roughgarden


Dynamic Subgraph Connectivity with Geometric Applications

Timothy M. Chan


Optimal Finger Search Trees in the Pointer Machine

Gerth S. Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas Tsichlas


Pseudo-Random Generators for all Hardnesses

Christopher Umans


Solving Convex Programs by Random Walks

Dimitris Bertsimas and Santosh Vempala


Limits to List Decodability of Linear Codes

Venkatesan Guruswami


Near-optimal Linear-Time Codes for Unique Decoding and New List-Decodable Codes Over Smaller Alphabets

Venkatesan Guruswami and Piotr Indyk


On the Advantage Over a Random Assignment

Johan Hastad and S. Venkatesh


A Unified Analysis of Hot Video Schedulers

Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting and Wai-Ha Wong