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.


For instructions on how to find the venue that the talks will take place, please follow this link.

09:00am-10:00am Invited speaker - Nathan Linial, The Hebrew University of Jerusalem

10:00am-10:20am Venkatesan Guruswami, James R. Lee, and Avi Wigderson. Euclidean Sections of L_1^N with Sublinear Randomness and Error-Correction Over the Reals

10:20am-10:40am Coffee break

10:40am-11:00am Avner Magen and Anastasios Zouzias. Near Optimal Dimensionality Reductions that Preserve Volumes
11:00am-11:20am Edo Liberty, Nir Ailon and Amit Singer. Dense Fast Random Projections and Lean Walsh Transforms
11:20am-11:40am Gregory Sorkin. The Power of Choice in a Generalized Polya Urn Model
11:40am-12:00pm Jeff Abrahamson, Bela Csaba, Ali Shokoufandeh. Optimal Random Matchings on Trees and Applications
12:00pm-12:20pm Hariharan Narayanan and Partha Niyogi. Sampling Hypersurfaces through Diffusion

12:20pm-02:00pm Lunch break

02:00pm-02:20pm Venkat Guruswami and Prasad Raghavendra. Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness
02:20pm-02:40pm Yuval Lando and Zeev Nutov. Inapproximability of Survivable Networks
02:40pm-03:00pm Micah Adler and Brent Heeringa. Approximating Optimal Binary Decision Trees
03:00pm-03:20pm Richard Matthew McCutchen and Samir Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity
03:20pm-03:40pm Shashi Mittal and Andreas S. Schulz. A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

03:40pm-04:00pm Coffee break

04:00pm-04:20pm Kai-Min Chung and Salil Vadhan. Tight Bounds for Hashing Block Sources
04:20pm-04:40pm Anup Rao and David Zuckerman. Extractors for Three Uneven-Length Sources
04:40pm-05:00pm Ariel Gabizon and Ronen Shaltiel. Increasing the Output Length of Zero-Error Dispersers
05:00pm-05:20pm Anup Rao. A 2-Source Almost-Extractor for Linear Entropy
05:20pm-05:40pm Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs

06:00pm Reception


09:00am-10:00am Invited speaker - Harald Räcke, University of Warwick

10:00am-10:20am Eden Chlamtac and Gyanit Singh. Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies

10:20:am-10:40am Coffee break

10:40am-11:00am Aravind Srinivasan. Budgeted allocations in the full-information setting
11:00am-11:20am Nir Halman, Chung-Lun Li, and David Simchi-Levi. Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
11:20am-11:40am Arash Asadpour, Uriel Feige and Amin Saberi. Santa Claus Meets Hypergraph Matchings
11:40am-12:00pm Monaldo Mastrolilli, Nikolaus Mutsanas and Ola Svensson. Approximating Single Machine Scheduling with Scenarios
12:00pm-12:20pm David R. Karger and Jacob Scott. Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP

12:20pm-02:00pm Lunch break

02:00pm-02:20pm Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman and Orly Yahalom.On the Query Complexity of Testing Orientations for being Eulerian
02:20pm-02:40pm Eric Blais. Improved Bounds for Testing Juntas
02:40pm-03:00pm Tali Kaufman, Simon Litsyn and Ning Xie. Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
03:00pm-03:20pm Homin Lee, Jeffrey Jackson, Rocco Servedio and Andrew Wan. Learning random monotone DNF
03:20pm-03:40pm Hang Dinh and Alexander Russell. Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

03:40pm-04:00pm Coffee break

04:00pm-04:20pm Zeev Nutov. Approximating Directed Weighted-Degree Constrained Networks
04:20pm-04:40pm Viswanath Nagarajan and R Ravi. The Directed Minimum Latency Problem
04:40pm-05:00pm Lukasz Kowalik and Marcin Mucha. Deterministic 7/8-approximation for the Metric Maximum TSP
05:00pm-05:20pm Thanh Nguyen. A simple LP relaxation for the Asymmetric Traveling Salesman Problem
05:20pm-05:40pm Adrian Dumitrescu and Minghui Jiang. Sweeping points


09:00am-10:00am Invited speaker - Anup Rao, Institute for Advanced Study, Princeton University

10:00am-10:20am Dan Gutfreund and Salil Vadhan. Limitations of Hardness vs. Randomness under Uniform Reductions

10:20am-10:40am Coffee break

10:40am-11:00am Noga Alon, Ido Ben Eliezer and Michael Krivelevich. Small sample spaces cannot fool low degree polynomials
11:00am-11:20am Vikraman Arvind and Partha Mukhopadhyay. Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
11:20am-11:40am Dan Gutfreund and Guy Rothblum. The Complexity of Local List Decoding
11:40am-12:00pm Eli Ben-Sasson and Michael Viderman. Tensor Products of Weakly Smooth Codes are Robust
12:00pm-12:20pm David Woodruff. Corruption and Recovery-Efficient Locally Decodable Codes

12:20pm-02:00pm Lunch break

02:00pm-02:20pm Mihai Buadoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos and Morteza Zadimoghaddam. Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
02:20pm-02:40pm Guy Kortsarz, Michael Langberg and Zeev Nutov. Approximating Maximum Subgraphs Without Short Cycles
02:40pm-03:00pm MohammadAli Safari and Mohammad Salavatipour. A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs
03:00pm-03:20pm Jean Cardinal and Eythan Levy. Connected Vertex Covers in Dense Graphs

03:20pm-03:40pm Coffee break

03:40pm-04:00pm Matei David, Toniann Pitassi and Emanuele Viola. Improved Separations between Nondeterministic and Randomized Multiparty Communication
04:00pm-04:20pm Raphael Yuster. Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
04:20pm-04:40pm Martin Fürer and Shiva Kasiviswanathan. Approximately Counting Embeddings into Random Graphs
04:40pm-05:00pm Guy Bresler, Elchanan Mossel and Allan Sly. Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
05:00pm-05:20pm Andrej Bogdanov, Elchanan Mossel and Salil Vadhan. The complexity of distinguishing Markov Random Fields

Valid XHTML 1.0 Transitional Valid CSS!

Maintained by Marios Karagiannis