List of accepted papers for RANDOM 2005:


Finding a maximum independent set in a sparse random graph
Uriel Feige and Eran Ofek

An Improved Analysis of Mergers
Zeev Dvir and Amir Shpilka

A lower bound for distribution-free monotonicity testing in the high dimensional case
Shirley Halevy and Eyal Kushilevitz

Testing Periodicity
Oded Lachish and Ilan Newman

Tight bounds for string reconstruction using substring queries
Dekel Tsur

On Learning Random DNF Formulas under the Uniform Distribution
Jeffrey C. Jackson and Rocco A. Servedio

Tolerant Locally Testable Codes
Venkatesan Guruswami and Atri Rudra

Fractional decompositions of dense hypergraphs
Raphael Yuster

Derandomized Constructions of k-Wise (Almost) Independent Permutations
Eyal Kaplan and Moni Naor and Omer Reingold

Reconstructive Dispersers and Hitting Set Generators
Christopher Umans

A Lower Bound on List Size for List Decoding
Venkatesan Guruswami and Salil Vadhan

The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem
Vadim Lyubashevsky

On the Error Parameter of Dispersers
Ronen Gradwohl and Guy Kindler and Omer Reingold and Amnon Ta-Shma

Average case analysis of DPLL for random decision problems
Remi MONASSON

The Online Clique Avoidance Game on Random Graphs
Martin Marciniszyn and Reto Spöhel and Angelika Steger

The Tensor Product of Two Codes is not Necessarily Robustly Testable
Paul Valiant

Sampling Bounds for Stochastic Optimization
Moses Charikar and Chandra Chekuri and Martin Pal

Bounds for error reduction with few quantum queries
Sourav Chakraborty and Jaikumar Radhakrishnan and Nandakumar Raghunathan

A Continuous-Discontinuous Transition in the Satisfiability of Random Horn Formulas
Cristopher Moore and Gabriel Istrate and Demetrios Demopoulos and Moshe Vardy

Derandomized Squaring of Graphs
Eyal Rozenman and Salil Vadhan

Mixing Points on a Circle
D. Randall and P. Winkler