Program Committee


Nikhil Bansal
Ziv Bar-Yossef
Artur Czumaj
Michel Goemans
Sudipto Guha
Magnus M. Halldorsson
Dorit Hochbaum
Elias Koutsoupias
Robert Krauthgamer
Ravi Kumar
Lap Chi Lau
Seffi Naor (chair)
Tim Roughgarden
Bruce Shepherd
Tami Tamir


Irit Dinur (chair)
Vitaly Feldman
Parikshit Gopalan
Danny Gutfreund
Prahladh Harsha
Avinatan Hassidim
Russel Impagliazzo
Mark Jerrum
Tali Kaufman
Subhash Khot
J. Radhakrishnan
Dana Randall
Michael Saks
Adi Shraibman
Emanuele Viola

Program Chairs

Seffi Naor,

Irit Dinur,
Weizmann Institute

Workshop Chairs

Klaus Jansen,
U. of Kiel

José Rolim,
U. of Geneva

Local Chairs

Neha Dave,
UC Berkeley
Important dates
Submission deadline
April 12, 2009

Notification to authors
June 1, 2009

Camera ready
June 15, 2009

August 21-23, 2009
Call for papers
Accepter Papers
Accepted papers in Random - Papers

  • Van Vu and Terence Tao. Smooth analysis of the condition number and the least singular value
  • Oded Goldreich and Dana Ron. Algorithmic Aspects of Property Testing in The Dense Graphs Model
  • Oded Goldreich, Michael Krivelevich, Ilan Newman and Eyal Rozenberg. Hierarchy Theorems for Property Testing
  • Alan Frieze, Pall Melsted and Michael Mitzenmacher. An Analysis of Random-Walk Cuckoo Hashing
  • Lorenz Minder and Danny Vilenchik. Small clique detection and approximate Nash equilibria
  • Ido Ben Eliezer, Rani Hod and Shachar Lovett. Random low degree polynomials are hard to approximate
  • Prasad Chebolu, Alan Frieze, Pall Melsted and Gregory Sorkin. Average-case analyses of Vickrey costs
  • Dana Ron and Gilad Tsur. Testing Computability by Width Two OBDDs
  • Adam Klivans, Philip Long and Alex Tang. Baum's Algorithm Learns Intersections of Halfspaces with respect to Log-Concave Distributions
  • Victor Chen. A Hypergraph Dictatorship Test with Perfect Completeness
  • Eli Ben-Sasson and Michael Viderman. Composition of semi-LTCs by two-wise Tensor Products
  • Klim Efremenko and Omer Reingold. How Well Do Random Walks Parallelize?
  • Amir Shpilka and Ilya Volkovich. Improved Polynomial Identity Testing for Read-Once Formulas
  • Ricky Rosen, Ran Raz, Boaz Barak, Anup Rao and Ronen Shaltiel. Strong Parallel Repetition Theorem for Free Projection Games
  • Elena Grigorescu, Tali Kaufman and Madhu Sudan. Succinct Representation of Codes with Applications to Testing
  • Noga Alon, Rina Panigrahy and Sergey Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem
  • Andrej Bogdanov and Youming Qiao. On the Security of Goldreich's One-Way Function
  • Brendan Lucier, Michael Molloy and Yuval Peres. The Glauber dynamics for colourings of bounded degree trees
  • S. Charles Brubaker and Santosh Vempala. Random Tensors and Planted Cliques
  • Aram Harrow and Richard Low. Efficient Quantum Tensor Product Expanders and k-designs
  • Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel. Pseudorandom Generators and Typically-Correct Derandomization
  • Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan. Pseudorandom Bit Generators that Fool Modular Sums
  • Karthekeyan Chandrasekaran, Amit Deshpande and Santosh Vempala. Sampling Harmonic Concave Functions: The Limit of Convexity Based Isoperimetry
  • Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing {-1,1}-Weight Halfspaces
  • Raghu Meka and David Zuckerman. Small-Bias Spaces for Group Products
  • Anindya De and Luca Trevisan. Extractors using hardness amplification
  • T.S. Jayram. Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND
  • Shubhangi Saraf and Swastik Kopparty. Tolerant Linearity Testing and Locally Testable Codes

Accepted papers in Approx - Papers

  • Ashkan Aazami, Joseph Cheriyan and Krishnam Raju Jampani. Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
  • Julia Chuzhoy and Paolo Codenotti. Resource Minimization Job Scheduling
  • Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese. Real-Time Message Routing and Scheduling
  • Katarzyna Paluch, Marcin Mucha and Aleksander Madry. A 7/9 Approximation Algorithm for the Maximum Traveling Salesman Problem
  • Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev and Maxim Sviridenko. On Hardness of Pricing Items for Single-Minded Bidders
  • Friedrich Eisenbrand and Thomas Rothvoss. New Hardness Results for Diophantine Approximation
  • Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Danny Segev. Scheduling with Outliers
  • Saurav Pandit, Sriram Pemmaraju and Kasturi Varadarajan. Approximation Algorithms for Domatic Partitions
  • Brian Tagiku, Adam Meyerson and Douglas Carroll. Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
  • Avner Magen and Mohammad Moharrami. Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy
  • Jon Lee, Maxim Sviridenko and Jan Vondrak. Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties
  • Chandra Chekuri and Iftah Gamzu. Truthful Mechanisms via Greedy Iterative Packing
  • Gaurav Kanade, Matt Gibson, Kasturi Varadarajan and Erik Krohn. An Approximation Scheme for Terrain Guarding
  • Venkatesan Guruswami and Ali Kemal Sinop. Improved Inapproximability Results for Maximum k-Colorable Subgraph
  • Chandra Chekuri, Alina Ene and Nitish Korula. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
  • Alexander Jaffe, James Lee and Mohammad Moharrami. On the optimality of gluing over scales
  • Rolf Harren and Rob van Stee. Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
  • Thomas Rothvoss and Laura Sanita. On the complexity of the asymmetric VPN problem
  • Jose R. Correa, Martin Skutella and Jose Verschae. The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
  • Brian Tagiku and Adam Meyerson. Minimizing Average Shortest Path Distances via Shortcut Edge Addition
  • Zeev Nutov. Approximating Node-Connectivity Augmentation Problems
  • Guy Kortsraz and Zeev Nutov. Approximating some network design problems with node costs
  • Konstantinos Georgiou, Avner Magen and Madhur Tulsiani. Optimal Sherali-Adams Gaps from Pairwise Independence
  • Uriel Feige, Nicole Immorlica, Vahab Mirrokni and Hamid Nazerzadeh. Pass Approximation: A Framework for Analyzing and Designing Heuristics
  • Ankit Aggarwal, Amit Deshpande and Ravi Kannan. Adaptive Sampling for k-means Clustering

Valid XHTML 1.0 Transitional Valid CSS!

Maintained by Marios Karagiannis