List of accepted papers for RANDOM 2002:


Rapidly mixing Markov chains for dismantleable constraint graphs
Martin Dyer, Mark Jerrum, and Eric Vigoda

Bisection of Random Cubic graphs
J. Diaz, N. Do, M. Serna, N.C. Wormald

Finding Sparse Induced Subgraphs of Semirandom Graphs
Amin Coja-Oghlan

Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes
Kenji Obata

Counting and Sampling H-colourings
Martin Dyer and Leslie Ann Goldberg and Mark Jerrum

\omega-regular Languages are Testable with a Constant Number of
Hana Chockler and Orna Kupferman

Small k-dominating Sets of Regular Graphs
William Duckworth and Bernard Mans

On Testing Convexity and Submodularity
Michal Parnas and Dana Ron and Ronitt Rubinfeld

Quantum Walks on the Hypercube
Christopher Moore and Alexander Russell

Is Constraint Satisfaction Over Two Variables Always Easy?
Lars Engebretsen and Venkatesan Guruswami

Classifying special interest groupsin web graphs
C. Cooper

Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View
Martin Dyer and Alistair Sinclair and Eric Vigoda and Dror Weitz

Derandomization that is rarely wrong from short advice that is typically good
Oded Goldreich and Avi Wigderson

Computing graph properties by randomized subcube partitions
Ehud Friedgut, Jeff Kahn, Avi Wigderson

Observations on Probabilistic-Time Hierarchy
Boaz Barak

Counting distinct elements in a data stream
Ziv Bar-Yossef and T. S. Jayram and Ravi Kumar and D. Sivakumar

Dimensionality Reductions that Preserve Volumes and Distance to Affine Spaces, and their Algorithmic Applications
Avner Magen

On the Eigenvalue Power Law
Milena Mihail and Christos Papadimitriou

Low-Randomness Characterizations of Two NP Proof Systems
Alfredo De Santis and Giovanni Di Crescenzo and Giuseppe Persiano

The two-colorability of random hypergraphs
Dimitris Achlioptas and Cris Moore

Percolation on Finite Cayley Graphs
Christopher Malon and Igor Pak