Program Committee


Chandra Chekuri
Uriel Feige
Pierre Fraigniaud
Magnús M. Halldórsson
Christos Kaklamanis
Anna Karlin
Samir Khuller
Guy Kortsarz
Monaldo Mastrolilli
Claire Mathieu
Zeev Nutov
Giuseppe Persiano
Maria Serna (chair)
Martin Skutella
Maxim Sviridenko
David P. Williamson


Dimitris Achlioptas
Alexandr Andoni
Anna Gal
Valentine Kabanets
Swastik Kopparty
Michael Krivelevich
Sofya Raskhodnikova
Ran Raz
Atri Rudra
Rocco Servedio
Ronen Shaltiel (chair)
Angelika Steger
Christopher Umans
Eric Vigoda
Sergey Yekhanin

Program Chairs

Maria Serna,
Universitat Politècnica de Catalunya

Ronen Shaltiel,
University of Haifa

Workshop Chairs

Klaus Jansen,
U. of Kiel

José Rolim,
U. of Geneva

Local Chairs

Maria Blesa,
Universitat Politècnica de Catalunya
Maria Serna,
Universitat Politècnica de Catalunya
Important dates
Submission deadline
April 18 , 2010

Notification to authors
June 12 , 2010

Camera ready
June 23 , 2010

1-3 September 2010
Call for papers
Accepter Papers
Accepted papers in Random - Papers

  • Arie Matsliah, Jop Briet, Sourav Chakraborty and David García-Soriano. Monotonicity Testing and Shortest-Path Routing on the Cube
  • Thomas Watson. Relativized Worlds Without Worst-Case to Average-Case Reductions for NP
  • Eli Ben-Sasson and Michael Viderman. Low Rate Is Insufficient for Local Testability
  • Suguru Tamaki and Yuichi Yoshida. A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness
  • Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick and Ronald de Wolf. Better Gap-Hamming Lower Bounds via Better Round Elimination
  • Oded Goldreich. On Testing Computability by Small Width OBDDs
  • Tali Kaufman and Michael Viderman. Locally Testable vs. Locally Decodable Codes
  • Yuichi Yoshida and Hiro Ito. Testing Outerplanarity of Bounded Degree Graphs
  • David Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
  • Dana Ron and Elya dolev. Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries
  • Aaron Roth. Differential Privacy and the Fat-Shattering Dimension of Linear Queries
  • Parikshit Gopalan and Rocco Servedio. Learning and Lower Bounds for AC^0 with Threshold Gates
  • Elazar Goldenberg and Irit Dinur. The Structure of Winning Strategies in Parallel Repetition Games
  • Eric Allender, V Arvind and Fengming Wang. Uniform Derandomization from Pathetic Lower Bounds
  • Rasmus R. Amossen, Andrea Campagna and Rasmus Pagh. Better size estimation for sparse matrix products
  • Amin Coja-Oghlan, Mikael Onsjö and Osamu Watanabe. Propagation Connectivity of Random Hypergraphs
  • Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders
  • Funda Ergun, Hossein Jowhari and Mert Saglam. Periodicity in Streams
  • Atri Rudra and Steve Uurtamo. Two Theorems on List Decoding
  • Piotr Indyk and Stanislaw Szarek. Almost-Euclidean subspaces of ell_1^N via tensor products: a simple approach to randomness reduction
  • Roy Kasher and Julia Kempe. Two-source Extractors Secure Against Quantum Adversaries
  • Noga Alon and Eric Blais. Testing boolean function isomorphism
  • Nayantara Bhatnagar, Allan Sly and Prasad Tetali. Reconstruction threshold for the hardcore model
  • Russell Impagliazzo and Valentine Kabanets. Constructive Proofs of Concentration Bounds
  • Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani. Improved Pseudorandom Generators for Depth 2 Circuits
  • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
  • Alistair Sinclair and Dan Vilenchik. Delaying satisfiability for random 2SAT
  • Thomas Hayes and Alistair Sinclair. Liftings of Tree-Structured Markov Chains
  • David Steurer. Improved Rounding for Parallel Repeated Unique Games

Accepted papers in Approx - Papers

  • Preyas Popat, Subhash Khot and Rishi Saket. Approximate Lasserre Integrality Gap for Unique Games
  • Ishay Haviv and Oded Regev. The Euclidean Distortion of Flat Tori
  • Irit Dinur and Igor Shinkar. On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors
  • Ken-ichi Kawarabayashi and Yusuke Kobayashi. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
  • Frank Kammer and Torsten Tholey. Approximation Algorithms for Intersection Graphs
  • Prasad Chebolu , Leslie Ann Goldberg and Russell Martin. The Complexity of Approximately Counting Stable Matchings
  • Spyros Kontogiannis and Paul Spirakis. Exploiting Concavity in Bimatrix Games: New polynomially tractable subclasses
  • MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Julian Mestre. The Checkpoint Problem
  • Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
  • Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson and Ola Svensson. Approximating Linear Threshold Predicates
  • Mohammad Hossein Bateni and Julia Chuzhoy . Approximation Algorithms for the Directed k-Stroll and k-Tour Problems
  • Mohit Singh and Kunal Talwar. Improving Integrality Gaps via \chvatal-Gomory Rounding
  • Per Austrin. Improved Inapproximability For Submodular Maximization
  • Piotr Berman and Sofya Raskhodnikova. Approximation Algorithms for Min-Max Generalization Problems
  • Igor Gorodezky, Robert Kleinberg, David Shmoys and Gwen Spencer. Improved lower bounds for the universal and a priori TSP
  • MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Morteza Zadimoghaddam . Submodular Secretary Problem and Extensions
  • Eden Chlamtac , Robert Krauthgamer and Prasad Raghavendra. Approximating Sparsest Cut in Graphs of Bounded Treewidth
  • Ken-ichi Kawarabayashi and Yusuke Kobayashi. Improved Algorithm for the Half-Disjoint Paths Problem
  • Lee-Ad Gottlieb and Tyler Neylon. Matrix sparsification and the sparse null space problem
  • Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam and Kunal Talwar. Vertex Sparsifiers: New Results from Old Techniques
  • Guyslain Naves, Nicolas Sonnerat and Adrian Vetta. Maximum Flows on Disjoint Paths
  • Piotr Indyk , Avner Magen, Anastasios Sidiropoulos and Anastasios Zouzias. On-line Embeddings
  • Hyung-Chan An, Robert D. Kleinberg and David B. Shmoys. Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
  • Victor Chepoi, Feodor Dragan, Ilan Newman, Yuri Rabinovich and Yann Vaxes. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
  • Thomas Erlebach and Erik Jan van Leeuwen. PTAS for Weighted Set Cover on Unit Squares
  • Evdokia Nikolova. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
  • Lee-Ad Gottlieb and Robi Krauthgamer. Proximity algorithms for nearly-doubling spaces
  • Gruia Calinescu. Min-Power Strong Connectivity