**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

E.Bachmat

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

3-MANIFOLD KNOT GENUS is
NP-complete

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