Program Committee


Julia Chuzoy
Naveen Garg
Michel Goemans
Fabrizio Grandoni
Anupam Gupta
Prahalad Harsha
Satoru Iwata
Philip Klein
Robert Krauthgammer
Kamesh Munagala
Zeev Nutov
R. Ravi (chair)
Guido Schaefer
Chaitanya Swamy
Kunal Talwar
Gerhard Woeginger


Per Austrin
Nayantara Bhatnagar
Amin Coja-Oghlan
Josep Diaz
Benjamin Doerr
Devdatt Dubhashi
Martin Dyer
Tom Friedetzky
Leslie Goldberg (chair)
Mark Jerrum
Elitza Maneva
Allan Sly
Eli Upfal
Juan Vera
Osamu Watanabe
David Zuckerman

Program Chairs

R. Ravi,
Carnegie Mellon University

Leslie Goldberg,
University of Liverpool

Workshop Chairs

José Rolim,
U. of Geneva
Klaus Jansen,
U. of Kiel
Important dates
Submission deadline
April 15, 2011

Notification to authors
June 8, 2011

Camera ready
June 17, 2011

August 17-19, 2011
Call for papers


    APPROX + RANDOM 2011 Program

    (download the program in PDF here)

    Every day, at 8:30am, there will be free breakfast available.

    August 17
      9:00-10:50 (Approx)
      Chair: R.Ravi
    • Johan Håstad. Satisfying degree d equations over GF[2]^n
    • Michael Kapralov and Rina Panigrahy. Multiplicative approximations of random walk transition probabilities
    • Sanjeev Arora and Rong Ge. New Tools for Graph Coloring
    • Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala. Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
    • Chandan Dubey and Thomas Holenstein. Approximating lattice problems using an approximate shortest vector oracle
    • 10:50-11:15 Coffee break
      11:15-13:10 (Random)
      Chair: Leslie Goldberg
    • Invited talk - Joel Spencer. Two Needles in Exponential Haystacks
    • Omri Weinstein, Ronitt Rubinfeld, Dana Ron and Muli Safra. Approximating the influence of a monotone Boolean function in $O(\sqrt{n})$ query complexity
    • Gilad Tsur and Dana Ron. On Approximating the Number of Relevant Variables in a Function
    • Dana Dachman-Soled and Rocco Servedio. A canonical form for testing Boolean function properties
    • 13:10-14:30 Lunch break (at your own)
      14:30-16:20 (Approx)
      Chair: Viswanath Nagarajan
    • Michael Crouch and Andrew Mcgregor. Periodicity and Cyclic Shifts via Linear Sketches
    • Khanh Do Ba and Piotr Indyk. Sparse recovery with partial support knowledge
    • Zhiyi Huang, Lei Wang and Yuan Zhou. Black-Box Reductions in Mechanism Design
    • Sagi Snir and Raphael Yuster. A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
    • Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Social Welfare in One-sided Matching Markets without Money
    • 16:20-16:45 Coffee break
      16:45-18:57 (Random)
      Chair: Eric Allender
    • Zhiyi Huang and Sampath Kannan. On Sampling from Multivariate Distributions
    • Nayantara Bhatnagar, Andrej Bogdanov and Elchanan Mossel. The Computational Complexity of Estimating MCMC Convergence Time
    • Sarah Miracle, Dana Randall and Amanda Pascoe Streib. Clustering in Interfering Models of Binary Mixtures
    • Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
    • Mohammed Abdullah, Colin Cooper and Moez Draief. Viral Processes by Random Walks on Random Graphs
    • Tobias Friedrich and Lionel Levine. Fast Simulation of Large-Scale Growth Models
    • 19:00 Welcome Reception
    August 18
      9:00-10:50 (Random)
      Chair: Oded Goldreich
    • Venkatesan Guruswami and Carol Wang. Optimal rate list decoding via derivative codes
    • Brett Hemenway, Martin Strauss, Rafail Ostrovsky and Mary Wootters. Public-Key Locally-Decodable Codes with Short Keys
    • Irit Dinur and Tali Kaufman. Dense locally testable codes cannot have constant rate and distance
    • Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes
    • Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan. On Sums of Locally Testable Affine Invariant Properties
    • 10:50-11:15 Coffee break
      11:15-13:10 (Approx)
      R. Ravi
    • David Williamson, Some Open Problems in Approximation Algorithms
    • Sushant Sachdeva and Rishi Saket. Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
    • Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
    • Per Austrin, Mark Braverman and Eden Chlamtac. Inapproximability of NP-Complete Variants of Nash Equilibrium
    • 13:10-14:30 Lunch break (at your own)
      14:30-16:20 (Random)
      Chair: Dana Ron
    • Lidor Avigad and Oded Goldreich. Testing Graph Blow-Up
    • Oded Goldreich and Tali Kaufman. Proximity Oblivious Testing and the Role of Invariances
    • Eldar Fischer and Eyal Rozenberg. Inflatable graph properties and natural property tests
    • Alan Edelman, Avinatan Hassidim, Huy Nguyen and Krzysztof Onak. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
    • Andris Ambainis, Andrew Childs and Yi-Kai Liu. Quantum property testing for bounded-degree graphs
    • 16:20-16:45 Coffee break
      16:45-18:57 (Approx)
      Chair: Deeparnab Chakrabarty
    • Feodor Dragan and Ekkehard Koehler. An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
    • Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman. Bandwidth and Low Dimensional Embedding
    • Adrian Dumitrescu, Minghui Jiang and Janos Pach. Opaque sets
    • Sandor Fekete, Tom Kamphans, Alexander Kroeller, Joseph Mitchell and Christiane Schmidt. Exploring and Triangulating a Region by a Swarm of Robots
    • Parinya Chalermsook. Coloring and Maximum Independent Set of Rectangles
    • Piotr Berman, Erik D. Demaine and Morteza Zadimoghaddam. O(1)-Approximations for Maximum Movement Problems
    August 19
      9:00-10:50 (Approx)
      Chair: Amit Kumar
    • Rohit Khandekar, Guy Kortsarz and Zeev Nutov. Approximating node-connectivity and prize-collecting network-design problems with degree constraints
    • Nachshon Cohen and Zeev Nutov. A $(1+\ln 2)$-approximation algorithm for minimum-cost $2$-edge-connectivity augmentation of trees with constant radius
    • Timothy Carnes and David Shmoys. Primal-Dual Schema and Lagrangian Relaxation for the k-Location Routing Problem
    • M. Reza Khani and Mohammad Salavatipour. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
    • Inge Li Gørtz and Viswanath Nagarajan. Locating Depots for Capacitated Vehicle Routing
    • 10:50-11:15 Coffee break
      11:15-13:05 (Random)
      Chair: Nayantara Bhatnagar
    • Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtech Rodl and Asaf Shapira. A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
    • Daniel Kane, Raghu Meka and Jelani Nelson. Almost Optimal Explicit Johnson-Lindenstrauss Transformations
    • Anindya De and Thomas Watson. Extractors and Lower Bounds for Locally Samplable Sources
    • Thomas Watson. Query Complexity in Errorless Hardness Amplification
    • Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
    • 13:10-14:30 Lunch break (at your own)
      14:30-16:20 (Approx)
      Chair:Zeev Nutov
    • Maurice Cheung and David Shmoys. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
    • Venkatesan Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. Scheduling Resources for Throughput Maximization
    • Marek Karpinski and Warren Schudy. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
    • Moran Feldman, Seffi Naor and Roy Schwartz. Improved Competitive Ratios for Submodular Secretary
    • Nikhil Bansal, Ravishankar Krishnaswamy and Barna Saha. On Capacitated Set Cover
    • 16:20-16:45 Coffee break
      16:45-18:35 (Random)
      Chair: Jose Rolim
    • Amit Chakrabarti and Ranganath Kondapally. Everywhere-Tight Information Cost Tradeoffs for Augmented Index
    • Andrew Drucker. Efficient Probabilistically Checkable Debates
    • Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC0 circuits with n^{1−o(1)} symmetric gates
    • Varsha Dani and Cristopher Moore. Independent sets in random graphs from the weighted second moment method
    • Joshua Brody and David Woodruff. Streaming Algorithms with One-Sided Estimation