Program Committee


Matthew Andrews
Timothy Chan
Julia Chuzhoy
Uriel Feige
Ashish Goel (Chair)
Elad Hazan
Stefano Leonardi
Aranyak Mehta
Vahab Mirrokni
Kamesh Munagala
Adi Rosen
David Shmoys
Adrian Vetta
Jan Vondrak
David Williamson


Nir Ailon
Tugkan Batu
Petra Berenbrink
Harry Buhrman
Amin Coja-Οghlan
Anna Gal
Yuval Ishai
David Kempe
Adam Klivans
Ronitt Rubinfeld (Chair)
Alex Samorodnitsky
Martin Strauss
Amir Shpilka
Eric Vigoda
David Woodruff

Program Chairs

Ashish Goel,
Stanford University

Ronitt Rubinfeld,

Workshop Chairs

Klaus Jansen,
U. of Kiel

José Rolim,
U. of Geneva
Important dates
Submission deadline
April 7, 2008

Notification to authors
May 23, 2008

Camera ready
June 15, 2008

August 25-27, 2008

Early registration
Before 4 August, 2008

Group rate valid until
August 8, 2008
Call for papers
Thank you

The Random/Approx organization would like to thank Microsoft Corporation for their support.

Accepted papers in Random - 27 Papers

  • 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 ε-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

Accepted papers in Approx - 20 Papers

  • Yuval Lando and Zeev Nutov. Inapproximability of Survivable Networks
  • Zeev Nutov. Approximating Directed Weighted-Degree Constrained Networks
  • Nir Halman and Chung-Lun Li. Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
  • Jean Cardinal and Eythan Levy. Connected Vertex Covers in Dense Graphs
  • Venkat Guruswami and Prasad Raghavendra. Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness
  • MohammadAli Safari and Mohammad Salavatipour. A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs
  • Richard Matthew McCutchen and Samir Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity
  • Guy Kortsarz, Michael Langberg and Zeev Nutov. Approximating Maximum Subgraphs Without Short Cycles
  • Aravind Srinivasan. Budgeted allocations in the full-information setting
  • Thanh Nguyen. A simple LP relaxation for the Asymmetric Traveling Salesman Problem
  • Mihai B\u{a}doiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos and Morteza Zadimoghaddam. Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
  • Eden Chlamtac and Gyanit Singh. Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies
  • Viswanath Nagarajan and R Ravi. The Directed Minimum Latency Problem
  • Monaldo Mastrolilli, Nikolaus Mutsanas and Ola Svensson. Approximating Single Machine Scheduling with Scenarios
  • Arash Asadpour, Uriel Feige and Amin Saberi. On Max-Min Fair Allocations and Hypergraph Matchings
  • Adrian Dumitrescu and Minghui Jiang. Sweeping points
  • Lukasz Kowalik and Marcin Mucha. Deterministic 7/8-approximation for the Metric Maximum TSP
  • Jacob Scott and David Karger. Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
  • Micah Adler and Brent Heeringa. Approximating Optimal Binary Decision Trees
  • Shashi Mittal and Andreas S. Schulz. A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

Valid XHTML 1.0 Transitional Valid CSS!

Maintained by Marios Karagiannis