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


    APPROX + RANDOM 2010 Program

    (download the program in PDF here)

    September 1st

    8h-9h Registration desk open

    Note: The registration Desk will be open on every break during the conference period

    9h-10h50am (Random)

    • Oded Goldreich. On Testing Computability by Small Width OBDDs
    • Noga Alon and Eric Blais. Testing boolean function isomorphism
    • Yuichi Yoshida and Hiro Ito. Testing Outerplanarity of Bounded Degree Graphs
    • Suguru Tamaki and Yuichi Yoshida. A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness
    • Dana Ron and Elya Dolev. Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries

    10h50-11h15am Coffee Break

    11h15 -1h10pm (Approx)

    • Leslie A Goldberg (invited talk). Approximating the Tutte polynomial of a graph
    • Per Austrin. Improved Inapproximability For Submodular Maximization
    • Preyas Popat, Subhash Khot and Rishi Saket. Approximate Lasserre Integrality Gap for Unique Games
    • Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson and Ola Svensson. Approximating Linear Threshold Predicates

    1h10pm-2h30pm Lunch

    2h30pm-4h20pm (Random)

    • Arie Matsliah, Jop Briet, Sourav Chakraborty and David Garci'a-Soriano. Monotonicity Testing and Shortest-Path Routing on the Cube
    • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
    • Funda Ergun, Hossein Jowhari and Mert Saglam. Periodicity in Streams
    • Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick and Ronald de Wolf. Better Gap-Hamming Lower Bounds via Better Round Elimination
    • Rasmus R. Amossen, Andrea Campagna and Rasmus Pagh. Better size estimation for sparse matrix products

    4h20pm-4h45pm Coffee Break

    4h45pm-6h35pm (Approx)

    • Mohammad Hossein Bateni and Julia Chuzhoy. Approximation Algorithms for the Directed k-Stroll and k-Tour Problems
    • Hyung-Chan An, Robert D. Kleinberg and David B. Shmoys. Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
    • Igor Gorodezky, Robert Kleinberg, David Shmoys and Gwen Spencer. Improved lower bounds for the universal and a priori TSP
    • Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Julian Mestre. The Checkpoint Problem
    • Thomas Erlebach and Erik Jan van Leeuwen. PTAS for Weighted Set Cover on Unit Squares

    9h30pm Conference dinner

    Restaurant: El Tunel del Port
    Address: Moll de Gregal 12, at the Olympic Harbor

    September 2nd

    9h-10h50am (Approx)

    • Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi and Morteza Zadimoghaddam . Submodular Secretary Problem and Extensions
    • Spyros Kontogiannis and Paul Spirakis. Exploiting Concavity in Bimatrix Games: New polynomially tractable subclasses
    • Piotr Berman and Sofya Raskhodnikova. Approximation Algorithms for Min-Max Generalization Problems
    • Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
    • Gruia Calinescu. Min-Power Strong Connectivity

    10h50-11h15am Coffee Break

    11h15 -1h10pm (Random)

    • Oded Goldreich (Invited talk). Some Thoughts regarding Unconditional Derandomization
    • Russell Impagliazzo and Valentine Kabanets. Constructive Proofs of Concentration Bounds
    • Elazar Goldenberg and Irit Dinur. The Structure of Winning Strategies in Parallel Repetition Games
    • David Steurer. Improved Rounding for Parallel Repeated Unique Games

    1h10pm-2h30pm Lunch

    2h30pm-4h20pm (Approx)

    • Irit Dinur and Igor Shinkar. On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors
    • Prasad Chebolu, Leslie Ann Goldberg and Russell Martin. The Complexity of Approximately Counting Stable Matchings
    • Evdokia Nikolova. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
    • Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam and Kunal Talwar. Vertex Sparsifiers: New Results from Old Techniques
    • Eden Chlamtac, Robert Krauthgamer and Prasad Raghavendra. Approximating Sparsest Cut in Graphs of Bounded Treewidth

    4h20pm-4h45pm Coffee Break

    4h45pm-6h57pm (Random)

    • Parikshit Gopalan and Rocco Servedio. Learning and Lower Bounds for AC0 with Threshold Gates
    • Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani. Improved Pseudorandom Generators for Depth 2 Circuits
    • Eric Allender, V Arvind and Fengming Wang. Uniform Derandomization from Pathetic Lower Bounds
    • Roy Kasher and Julia Kempe. Two-source Extractors Secure Against Quantum Adversaries
    • Piotr Indyk and Stanislaw Szarek. Almost-Euclidean subspaces of ell_1^N via tensor products: a simple approach to randomness reduction
    • Aaron Roth. Differential Privacy and the Fat-Shattering Dimension of Linear Queries

    September 3rd

    9h-10h50am (Random)

    • Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders
    • Amin Coja-Oghlan, Mikael Onsjo and Osamu Watanabe. Propagation Connectivity of Random Hypergraphs
    • Nayantara Bhatnagar, Allan Sly and Prasad Tetali. Reconstruction threshold for the hardcore model
    • Thomas Hayes and Alistair Sinclair. Liftings of Tree-Structured Markov Chains
    • Alistair Sinclair and Dan Vilenchik. Delaying satisfiability for random 2SAT

    10h50-11h15am Coffee Break

    11h15 -1h05pm (Approx)

    • Ishay Haviv and Oded Regev. The Euclidean Distortion of Flat Tori
    • Lee-Ad Gottlieb and Tyler Neylon. Matix sparsification and the sparse null space problem
    • Ken-ichi Kawarabayashi and Yusuke Kobayashi. Improved Algorithm for the Half-Disjoint Paths Problem
    • Guyslain Naves, Nicolas Sonnerat and Adrian Vetta. Maximum Flows on Disjoint Paths
    • 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

    1h10pm-2h30pm Lunch

    2h30pm-4h20pm (Random)

    • Tali Kaufman and Michael Viderman. Locally Testable vs. Locally Decodable Codes
    • Eli Ben-Sasson and Michael Viderman. Low Rate Is Insufficient for Local Testability
    • David Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
    • Atri Rudra and Steve Uurtamo. Two Theorems on List Decoding
    • Thomas Watson. Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

    4h20pm-4h45pm Coffee Break

    4h45pm-6h35pm (Approx)

    • Mohit Singh and Kunal Talwar. Improving Integrality Gaps via \chvatal-Gomory Rounding
    • Lee-Ad Gottlieb and Robi Krauthgamer. Proximity algorithms for nearly-doubling spaces
    • Frank Kammer,Heiko Voepel and Torsten Tholey. Approximation Algorithms for Intersection Graphs
    • Piotr Indyk, Avner Magen, Anastasios Sidiropoulos and Anastasios Zouzias. On-line Embeddings
    • Victor Chepoi, Feodor Dragan, Ilan Newman, Yuri Rabinovich and Yann Vaxes. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs