List of accepted papers for RANDOM 2006:


Oded Lachish, Ilan Newman and Asaf Shapira.
Space Complexity vs. Query Complexity

Sharon Marko and Dana Ron.
Distance Approximation in Bounded-Degree and General Sparse Graphs

Dana Ron and Oded Goldreich.
Approximating Average Parameters of Graphs

Martin Dyer, Leslie Goldberg and Mark Jerrum.
Dobrushin conditions and Systematic Scan

Avner magen, Shlomo hoory and Toniann Pitassi.
Monotone circuits for the majority function

Irit Dinur, Madhu Sudan and Avi Wigderson.
Robust local testability of tensor products of LDPC

Rajeev Motwani, Rina Panigrahy and Ying Xu.
Fractional Matching via Balls-and-Bins

Uriel Feige, Elchanan Mossel and Dan Vilenchik.
Complete convergence of message passing algorithms for some satisfiability problems

Amit Deshpande and Santosh Vempala.
Adaptive Sampling and Fast Low-Rank Matrix Approximation

Petros Drineas, Michael Mahoney and S. (Muthu) Muthukrishnan.
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

Sanjeev Arora, Elad Hazan and Satyen Kale.
A Fast Random Sampling Algorithm for Sparsifying Matrices

Murali Ganapathy.
Robust Mixing Time

Alexander Healy.
Randomness-Efficient Sampling within NC1

Thomas Strohmer and Roman Vershynin.
A randomized solver for linear systems with exponential convergence

Nayantara Bhatnagar, Sam Greenberg and Dana Randall.
The Effect of Boundary Conditions on Mixing Rates of Markov Chains

Dan Gutfreund.
Optimal worst-case to average-case reductions within the polynomial-time hierarchy

Martin Marciniszyn, Jozef Skokan, Reto Spöhel and Angelika Steger
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques

Elena Grigorescu, Swastik Kopparty and Madhu Sudan.
Local Decoding and Testing for Homomorphisms

Philipp Woelfel.
Maintaining External Memory Efficient Hash Tables

Yi-Kai Liu, Vadim Lyubashevsky and Daniele Micciancio.
On Bounded Distance Decoding for General Lattices

Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
On Pseudorandom Generators with Linear Stretch in NC0

Yi-Kai Liu.
Consistency of Local Density Matrices is QMA-complete