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