List of accepted papers for RANDOM 2009:


Van Vu and Terence Tao. 
Smooth analysis of the condition number and the least singular value

Oded Goldreich and Dana Ron. 
Algorithmic Aspects of Property Testing in The Dense Graphs Model

Oded Goldreich, Michael Krivelevich, Ilan Newman and Eyal Rozenberg. 
Hierarchy Theorems for Property Testing

Alan Frieze, Pall Melsted and Michael Mitzenmacher. 
An Analysis of Random-Walk Cuckoo Hashing

Lorenz Minder and Danny Vilenchik. 
Small clique detection and approximate Nash equilibria

Ido Ben Eliezer, Rani Hod and Shachar Lovett. 
Random low degree polynomials are hard to approximate

Prasad Chebolu, Alan Frieze, Pall Melsted and Gregory Sorkin. 
Average-case analyses of Vickrey costs

Dana Ron and Gilad Tsur. 
Testing Computability by Width Two OBDDs

Adam Klivans, Philip Long and Alex Tang. 
Baum's Algorithm Learns Intersections of Halfspaces with respect to Log-Concave Distributions

Victor Chen. 
A Hypergraph Dictatorship Test with Perfect Completeness

Eli Ben-Sasson and Michael Viderman. 
Composition of semi-LTCs by two-wise Tensor Products

Klim Efremenko and Omer Reingold. 
How Well Do Random Walks Parallelize?

Amir Shpilka and Ilya Volkovich. 
Improved Polynomial Identity Testing for Read-Once Formulas

Ricky Rosen, Ran Raz, Boaz Barak, Anup Rao and Ronen Shaltiel. 
Strong Parallel Repetition Theorem for Free Projection Games

Elena Grigorescu, Tali Kaufman and Madhu Sudan. 
Succinct Representation of Codes with Applications to Testing

Noga Alon, Rina Panigrahy and Sergey Yekhanin. 
Deterministic Approximation Algorithms for the Nearest Codeword Problem

Andrej Bogdanov and Youming Qiao. 
On the Security of Goldreich's One-Way Function

Brendan Lucier, Michael Molloy and Yuval Peres. 
The Glauber dynamics for colourings of bounded degree trees

S. Charles Brubaker and Santosh Vempala. 
Random Tensors and Planted Cliques

Aram Harrow and Richard Low. 
Efficient Quantum Tensor Product Expanders and k-designs

Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel. 
Pseudorandom Generators and Typically-Correct Derandomization

Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan. 
Pseudorandom Bit Generators that Fool Modular Sums

Karthekeyan Chandrasekaran, Amit Deshpande and Santosh Vempala. 
Sampling Harmonic Concave Functions: The Limit of Convexity Based Isoperimetry

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. 
Testing {-1,1}-Weight Halfspaces

Raghu Meka and David Zuckerman. 
Small-Bias Spaces for Group Products

Anindya De and Luca Trevisan. 
Extractors using hardness amplification

T.S. Jayram. 
Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND

Shubhangi Saraf and Swastik Kopparty. 
Tolerant Linearity Testing and Locally Testable Codes