Program Committee


Nikhil Bansal
Chandra Chekuri
Eden Chlamtac
Nikhil Devanur
Uriel Feige
Claire Mathieu
Ankur Moitra
Seffi Naor
Yuval Rabani
Prasad Raghavendra (chair)
Roy Schwartz
Mohit Singh
Ola Svensson
Mohammadtaghi Hajiaghayi
Madhur Tulsiani
Rico Zenklusen


Amit Chakrabarti
Nikolaos Fountoulakis
Ariel Gabizon
Parikshit Gopalan
Dan Gutfreund
Prahladh Harsha
Thomas Hayes
Michael Krivelevich
Shachar Lovett
Russell Martin
Dieter van Melkebeek
Sofya Raskhodnikova(Chair)
Shubhangi Saraf
Christian Sohler
David P. Woodruff
Amir Yehudayoff

Program Chairs

Prasad Raghavendra,
University of California, Berkeley

Sofya Raskhodnikova,
Pennsylvania State University

Workshop Chairs

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

Notification to authors
June 11, 2013

Camera ready
June 18, 2013
Call for papers


    APPROX + RANDOM 2012 Program

    (download the program in PDF here)

      Wed August 21

      8:45-10:13 RANDOM (Property testing and sublinear-time algorithms)

    • An optimal lower bound for monotonicity testing over hypergrids - Deeparnab Chakrabarty and C. Seshadhri
    • Testing Membership in Counter Automaton Languages - Yonatan Goldhirsh and Michael Viderman
    • Tight lower bounds for testing linear isomorphism - Elena Grigorescu, Karl Wimmer and Ning Xie
    • Local reconstructors and tolerant testers for connectivity and diameter - Andrea Campagna, Alan Guo and Ronitt Rubinfeld

    • 10:13-10:30 break

      10:30-11:30 Invited talk: Luca Trevisan
    • Title: Spectral Graph Theory
      Abstract: Spectral graph theory is the study of the combinatorial graph properties that can be derived by considering the eigenvalues and eigenvectors of the adjacency matrix of a graph. Such study leads to fast (both in theory and practice) approximation algorithms for graph partitioning problems, and to sufficient conditions to prove that certain graphs are expanders and that certain random walks converge quickly. We survey recent progress in this area, and its applications to approximation algorithms for small-set expansion, sparsest cut, and clustering problem

    • 11:30-12:14 RANDOM (Differential privacy)

    • Fast Private Data Release Algorithms for Sparse Queries - Avrim Blum and Aaron Roth
    • Private Learning and Sanitization: Pure vs. Approximate Differential Privacy - Amos Beimel, Kobbi Nissim and Uri Stemmer

    • 12:14-13:45 lunch break

      13:45-15:13 APPROX

    • Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions  - Kyle Fox, Sungjin Im, Janardhan Kulkarni and Benjamin Moseley
    • The Online Stochastic Generalized Assignment Problem - Saeed Alaei, Mohammadtaghi Hajiaghayi and Vahid Liaghat
    • Online Multidimensional Load Balancing - Adam Meyerson, Alan Roytman and Brian Tagiku
    • Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems - Pierre Fraigniaud, Magnus M. Halldorsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosen

    • 15:13-15:30 Break

      15:30-16:36 RANDOM (Streaming, sampling and population recovery)

    • A Tight Lower Bound for High Frequency Moment Estimation with Small Error - Yi Li and David Woodruff
    • What you can do with Coordinated Samples - Edith Cohen and Haim Kaplan
    • Finding Heavy Hitters from Partial or Noisy Data - Lucia Batman, Russell Impagliazzo, Cody Murray and Ramamohan Paturi

    • 16:36-16:55 Break

      16:55-18:01 APPROX

    • On the total perimeter of homothetic convex bodies in a convex container -  Adrian Dumitrescu and Csaba Toth
    • A pseudo-approximation for the genus of Hamiltonian graphs  - Yury Makarychev, Amir Nayyeri and Anastasios Sidiropoulos
    • Interdiction Problems on Planar Graphs  - Feng Pan and Aaron Schild

    • 18:30-20:00 Reception

      Thurs August 22

      8:45-10:13 APPROX

    • Multiple Traveling Salesmen in Asymmetric Metrics - Zachary Friggstad
    • Approximation Algorithms for Movement Repairmen  - Mohammadtaghi Hajiaghayi, Rohit Khandekar, Reza Khani and Guy Kortsarz
    • The Approximability of the Binary Paintshop Problem  - Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket and Baruch Schieber
    • Capacitated Network Design on Undirected Graphs - Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li and Srivatsan Narayanan

    • 10:13-10:30 Break

      10:30-11:30 Invited talk:Santosh Vempala
    • Title: High-dimensional Sampling Algorithms
      Abstract: Efficiently sampling high-dimensional distributions is a basic algorithmic problem with applications to optimization, integration/counting and learning. This talk will survey the state-of-the-art of randomized sampling algorithms and the main ideas involved, including geometric random walks, simulated annealing, isoperimetric inequalities and concentration of measure.

    • 11:30-12:14 APPROX

    • Improved Hardness of Approximating Chromatic Number - Sangxia Huang
    • On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems  - Per Austrin, Rajsekar Manokaran and Cenny Wenner

    • 12:14-13:45 Lunch break

      13:45-15:13 RANDOM (Random structures)

    • The Power of Choice for Random Satisfiability - Varsha Dani, Josep Diaz, Thomas Hayes and Cristopher Moore
    • On the average sensitivity and density of $k$-CNF formulas - Dominik Scheder and Li-Yang Tan
    • Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration - Emmanuel Abbe and Andrea Montanari
    • Connectivity of Random High Dimensional Geometric Graphs - Roee David and Uriel Feige

    • 15:13-15:30 Break

      15:30-16:36 APPROX

    • Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback  - Sudipto Guha and Kamesh Munagala
    • Scheduling Subset Tests: One-time, Continuous, and How They Relate - Edith Cohen, Haim Kaplan and Yishay Mansour
    • Online Square-into-Square Packing -Sandor Fekete and Hella-Franziska Hoffmann

    • 16:36-16:55 Break

      16:55-18:01 RANDOM (Multi-spin systems and the hard-core model) 

    • Improved FPTAS for Multi-Spin Systems  - Pinyan Lu and Yitong Yin
    • Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions - Juan Vera, Eric Vigoda and Linji Yang
    • Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2 - Antonio Blanca, David Galvin, Dana Randall and Prasad Tetali

    • Fri August 23

      8:45-10:13 RANDOM 4 (Error-Correcting Codes)

    • Absolutely Sound Testing of Lifted Codes - Noga Ron-Zewi, Elad Haramaty and Madhu Sudan
    • Zero Knowledge LTCs and Their Applications - Yuval Ishai, Amit Sahai, Michael Viderman and Mor Weiss
    • Matching-Vector Families and LDCs Over Large Modulo - Zeev Dvir and Guangda Hu
    • Combinatorial limitations of average-radius list decoding - Venkatesan Guruswami and Srivatsan Narayanan

    • 10:13-10:30 Break

      10:30-11:30 Invited talk: Persi Diaconis
    • Title: Connections between probability and algorithms
      Abstract: Computer scientists sometimes use probability for analysis of average case behavior of algorithms. I will describe some examples going in the opposite direction---algorithms giving new probability theory. One example is drawn from my recent work with Bobbie Chen, Daniel Kane and Rob Rhoades: the distribution of the number of crossings in a typical set partition seemed intractable, a clever algorithm of Stam for random generation saves the day.

    • 11:30-12:14 RANDOM (Randomness expansion and derandomization)

    • Robust Randomness Amplifiers: Upper and Lower Bounds - Matthew Coudron, Thomas Vidick and Henry Yuen
    • Randomness-Efficient Curve Samplers - Zeyu Guo

    • 12:14-13:45 Lunch break

      13:45-15:13 APPROX

    • Sketching Earth-Mover Distance on Graph Metrics  - Andrew McGregor and Daniel Stubbs
    • Spectral Sparsification in Dynamic Graph Streams  - Kook Jin Ahn, Sudipto Guha and Andrew McGregor
    • Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams  - Vladimir Braverman and Rafail Ostrovsky
    • Approximating Large Frequency Moments with Pick-and-Drop Sampling  - Vladimir Braverman and Rafail Ostrovsky
    • A local computation approximation scheme to maximum matching  - Yishay Mansour and Shai Vardi

    • 15:13-15:30 Break

      15:30-16:36 RANDOM (Derandomization and pseudorandomness)

    • Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem - Sixia Chen, Cristopher Moore and Alexander Russell
    • Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing- Michael A. Forbes and Amir Shpilka
    • Pseudorandomness for Regular Branching Programs via Fourier Analysis  - Omer Reingold, Thomas Steinke and Salil Vadhan

    • 16:36-16:55 Break

      16:55-17:40 APPROX

    • A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs  - Shayan Oveis Gharan and Luca Trevisan
    • Partial Interval Set Cover Trade-offs Between Scalability and Optimality - Katherine Edwards, William Kennedy and Simon Griffiths

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Eugenio Noto