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
Accepter Papers
Accepted papers in Random - Papers

  • Lidor Avigad and Oded Goldreich. Testing Graph Blow-Up
  • Thomas Watson. Query Complexity in Errorless Hardness Amplification
  • 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
  • Anindya De and Thomas Watson. Extractors and Lower Bounds for Locally Samplable Sources
  • Omri Weinstein, Ronitt Rubinfeld, Dana Ron and Muli Safra. Approximating the influence of a monotone Boolean function in $O(\sqrt{n})$ query complexity
  • Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes
  • Gilad Tsur and Dana Ron. On Approximating the Number of Relevant Variables in a Function
  • Nayantara Bhatnagar, Andrej Bogdanov and Elchanan Mossel. The Computational Complexity of Estimating MCMC Convergence Time
  • Dana Dachman-Soled and Rocco Servedio. A canonical form for testing Boolean function properties
  • Irit Dinur and Tali Kaufman. Dense locally testable codes cannot have constant rate and distance
  • Andris Ambainis, Andrew Childs and Yi-Kai Liu. Quantum property testing for bounded-degree graphs
  • Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtech Rodl and Asaf Shapira. A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
  • Varsha Dani and Cristopher Moore. Independent sets in random graphs from the weighted second moment method
  • Brett Hemenway, Martin Strauss, Rafail Ostrovsky and Mary Wootters. Public-Key Locally-Decodable Codes with Short Keys
  • Amit Chakrabarti and Ranganath Kondapally. Everywhere-Tight Information Cost Tradeoffs for Augmented Index
  • Venkatesan Guruswami and Carol Wang. Optimal rate list decoding via derivative codes
  • Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan. On Sums of Locally Testable Affine Invariant Properties
  • Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC0 circuits with n^{1−o(1)} symmetric gates
  • Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
  • Sarah Miracle, Dana Randall and Amanda Pascoe Streib. Clustering in Interfering Models of Binary Mixtures
  • Zhiyi Huang and Sampath Kannan. On Sampling from Multivariate Distributions
  • Tobias Friedrich and Lionel Levine. Fast Simulation of Large-Scale Growth Models
  • Alan Edelman, Avinatan Hassidim, Huy Nguyen and Krzysztof Onak. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
  • Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
  • Andrew Drucker. Efficient Probabilistically Checkable Debates
  • Daniel Kane, Raghu Meka and Jelani Nelson. Almost Optimal Explicit Johnson-Lindenstrauss Transformations
  • Joshua Brody and David Woodruff. Streaming Algorithms with One-Sided Estimation
  • Mohammed Abdullah, Colin Cooper and Moez Draief. Viral Processes by Random Walks on Random Graphs

Accepted papers in Approx - Papers

  • Michael Crouch and Andrew Mcgregor. Periodicity and Cyclic Shifts via Linear Sketches
  • Adrian Dumitrescu, Minghui Jiang and Janos Pach. Opaque sets
  • Nachshon Cohen and Zeev Nutov. A $(1+\ln 2)$-approximation algorithm for minimum-cost $2$-edge-connectivity augmentation of trees with constant radius
  • Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman. Bandwidth and Low Dimensional Embedding
  • Timothy Carnes and David Shmoys. Primal-Dual Schema and Lagrangian Relaxation for the k-Location Routing Problem
  • Sanjeev Arora and Rong Ge. New Tools for Graph Coloring
  • Johan Håstad. Satisfying degree d equations over GF[2]^n
  • Sagi Snir and Raphael Yuster. A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
  • Sandor Fekete, Tom Kamphans, Alexander Kroeller, Joseph Mitchell and Christiane Schmidt. Exploring and Triangulating a Region by a Swarm of Robots
  • Venkatesan Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. Scheduling Resources for Throughput Maximization
  • Michael Kapralov and Rina Panigrahy. Multiplicative approximations of random walk transition probabilities
  • Maurice Cheung and David Shmoys. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
  • M. Reza Khani and Mohammad Salavatipour. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
  • Feodor Dragan and Ekkehard Koehler. An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
  • Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
  • Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Social Welfare in One-sided Matching Markets without Money
  • Rohit Khandekar, Guy Kortsarz and Zeev Nutov. Approximating node-connectivity and prize-collecting network-design problems with degree constraints
  • Chandan Dubey and Thomas Holenstein. Approximating lattice problems using an approximate shortest vector oracle
  • Moran Feldman, Seffi Naor and Roy Schwartz. Improved Competitive Ratios for Submodular Secretary Problems
  • Inge Li Gørtz and Viswanath Nagarajan. Locating Depots for Capacitated Vehicle Routing
  • Parinya Chalermsook. Coloring and Maximum Independent Set of Rectangles
  • Piotr Berman, Erik D. Demaine and Morteza Zadimoghaddam. O(1)-Approximations for Maximum Movement Problems
  • Zhiyi Huang, Lei Wang and Yuan Zhou. Black-Box Reductions in Mechanism Design
  • Sushant Sachdeva and Rishi Saket. Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
  • Per Austrin, Mark Braverman and Eden Chlamtac. Inapproximability of NP-Complete Variants of Nash Equilibrium
  • Marek Karpinski and Warren Schudy. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
  • Nikhil Bansal, Ravishankar Krishnaswamy and Barna Saha. On Capacitated Set Cover Problems
  • Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala. Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions
  • Khanh Do Ba and Piotr Indyk. Sparse recovery with partial support knowledge

Valid XHTML 1.0 Transitional Valid CSS!

Maintained by Marios Karagiannis