List of accepted papers for RANDOM 2008:


Guy Bresler, Elchanan Mossel and Allan Sly. 
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms 

Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman and Orly Yahalom.
On the Query Complexity of Testing Orientations for being Eulerian 

Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. 
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs 

Raphael Yuster. 
Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets 

Homin Lee, Jeffrey Jackson, Rocco Servedio and Andrew Wan. 
Learning random monotone DNF 

Edo Liberty, Nir Ailon and Amit Singer. 
Dense Fast Random Projections and Lean Walsh Transforms 

David Woodruff. 
Corruption and Recovery-Efficient Locally Decodable Codes 

Noga Alon, Ido Ben Eliezer and Michael Krivelevich. 
Small sample spaces cannot fool low degree polynomials 

Andrej Bogdanov, Elchanan Mossel and Salil Vadhan. 
The complexity of distinguishing Markov Random Fields 

Hariharan Narayanan and Partha Niyogi. 
Sampling Hypersurfaces through Diffusion 

Tali Kaufman, Simon Litsyn and Ning Xie. 
Breaking the e-Soundness Bound of the Linearity Test over GF(2) 

Ariel Gabizon and Ronen Shaltiel. 
Increasing the Output Length of Zero-Error Dispersers 

Matei David, Toniann Pitassi and Emanuele Viola. 
Improved Separations between Nondeterministic and Randomized Multiparty Communication 

Vikraman Arvind and Partha Mukhopadhyay. 
Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size 

Venkat Guruswami, James Lee and Avi Wigderson. 
Euclidean sections of L_1^N with sublinear randomness and error-correcting codes over the reals 

Eli Ben-Sasson and Michael Viderman. 
Tensor Products of Weakly Smooth Codes are Robust 

Hang Dinh and Alexander Russell. 
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs 

Dan Gutfreund and Salil Vadhan. 
Limitations of Hardness vs. Randomness under Uniform Reductions 

Martin Fürer and Shiva Kasiviswanathan. 
Approximately Counting Embeddings into Random Graphs 

Anup Rao and David Zuckerman. 
Extractors for Three Uneven-Length Sources 

Anup Rao. 
A 2-Source Almost-Extractor for Linear Entropy 

Dan Gutfreund and Guy Rothblum. 
The Complexity of Local List Decoding 

Eric Blais. 
Improved Bounds for Testing Juntas 

Kai-Min Chung and Salil Vadhan. 
Tight Bounds for Hashing Block Sources 

Avner Magen and Anastasios Zouzias. 
Nearly tight dimensionality reductions the preserve volumes 

Bela Csaba and Ali Shokoufandeh. 
Optimal Random Matchings on Trees and Application 

Gregory Sorkin. 
The Power of Choice in a Generalized Polya Urn Model