List of accepted papers for RANDOM 2011:


Lidor Avigad and Oded Goldreich. 
Testing Graph Blow-Up

Thomas Watson. 
Query Complexity in Errorless Hardness Amplification

Oded Goldreich and Tali Kaufman. 
Proximity Oblivious Testing and the Role of Invariances

Eldar Fischer and Eyal Rozenberg. 
Inflatable graph properties and natural property tests

Anindya De and Thomas Watson. 
Extractors and Lower Bounds for Locally Samplable Sources

Omri Weinstein, Ronitt Rubinfeld, Dana Ron and Muli Safra. 
Approximating the influence of a monotone Boolean function in $O(\sqrt{n})$ query complexity

Eli Ben-Sasson and Madhu Sudan. 
Limits on the rate of locally testable affine-invariant codes

Gilad Tsur and Dana Ron. 
On Approximating the Number of Relevant Variables in a Function

Nayantara Bhatnagar, Andrej Bogdanov and Elchanan Mossel. 
The Computational Complexity of Estimating MCMC Convergence Time

Dana Dachman-Soled and Rocco Servedio. 
A canonical form for testing Boolean function properties

Irit Dinur and Tali Kaufman. 
Dense locally testable codes cannot have constant rate and distance

Andris Ambainis, Andrew Childs and Yi-Kai Liu. 
Quantum property testing for bounded-degree graphs

Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtech Rodl and Asaf Shapira. 
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma

Varsha Dani and Cristopher Moore. 
Independent sets in random graphs from the weighted second moment method

Brett Hemenway, Martin Strauss, Rafail Ostrovsky and Mary Wootters. 
Public-Key Locally-Decodable Codes with Short Keys

Amit Chakrabarti and Ranganath Kondapally. 
Everywhere-Tight Information Cost Tradeoffs for Augmented Index

Venkatesan Guruswami and Carol Wang. 
Optimal rate list decoding via derivative codes

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan. 
On Sums of Locally Testable Affine Invariant Properties

Shachar Lovett and Srikanth Srinivasan. 
Correlation bounds for poly-size AC0 circuits with n^{1-o(1)} symmetric gates

Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda and Linji Yang. 
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model

Sarah Miracle, Dana Randall and Amanda Pascoe Streib. 
Clustering in Interfering Models of Binary Mixtures

Zhiyi Huang and Sampath Kannan. 
On Sampling from Multivariate Distributions

Tobias Friedrich and Lionel Levine. 
Fast Simulation of Large-Scale Growth Models

Alan Edelman, Avinatan Hassidim, Huy Nguyen and Krzysztof Onak. 
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs

Sergei Artemenko and Ronen Shaltiel. 
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Andrew Drucker. 
Probabilistically Checkable Debates of Nearly-Linear Size

Daniel Kane, Raghu Meka and Jelani Nelson. 
Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Joshua Brody and David Woodruff. 
Streaming Algorithms with One-Sided Estimation

Mohammed Abdullah, Colin Cooper and Moez Draief. 
Viral Processes by Random Walks on Random Graphs