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

  • Combinatorial limitations of average-radius list decoding
    Venkatesan Guruswami and Srivatsan Narayanan.

  • Fast Private Data Release Algorithms for Sparse Queries
    Avrim Blum and Aaron Roth.

  • What you can do with Coordinated Samples
    Edith Cohen and Haim Kaplan.

  • Local reconstructors and tolerant testers for connectivity and diameter
    Andrea Campagna, Alan Guo and Ronitt Rubinfeld.

  • Testing Membership in Counter Automaton Languages
    Yonatan Goldhirsh and Michael Viderman.

  • Absolutely Sound Testing of Lifted Codes
    Noga Ron-Zewi, Elad Haramaty and Madhu Sudan.

  • Randomness-Efficient Curve Samplers
    Zeyu Guo.

  • Matching-Vector Families and LDCs Over Large Modulo
    Zeev Dvir and Guangda Hu.

  • An optimal lower bound for monotonicity testing over hypergrids
    Deeparnab Chakrabarty and C. Seshadhri.

  • Zero Knowledge LTCs and Their Applications
    Yuval Ishai, Amit Sahai, Michael Viderman and Mor Weiss.

  • 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.

  • Connectivity of Random High Dimensional Geometric Graphs
    Roee David and Uriel Feige.

  • Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2
    Antonio Blanca, David Galvin, Dana Randall and Prasad Tetali.

  • Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
    Michael A. Forbes and Amir Shpilka.

  • The Power of Choice for Random Satisfiability
    Varsha Dani, Josep Diaz, Thomas Hayes and Cristopher Moore.

  • Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
    Amos Beimel, Kobbi Nissim and Uri Stemmer.

  • Finding Heavy Hitters from Partial or Noisy Data
    Lucia Batman, Russell Impagliazzo, Cody Murray and Ramamohan Paturi.

  • On the average sensitivity and density of k-CNF formulas
    Dominik Scheder and Li-Yang Tan.

  • Robust Randomness Amplifiers: Upper and Lower Bounds
    Matthew Coudron, Thomas Vidick and Henry Yuen.

  • A Tight Lower Bound for High Frequency Moment Estimation with Small Error
    Yi Li and David Woodruff.

  • Tight lower bounds for testing linear isomorphism
    Elena Grigorescu, Karl Wimmer and Ning Xie.

  • Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem
    Sixia Chen, Cristopher Moore and Alexander Russell.

  • Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
    Emmanuel Abbe and Andrea Montanari.

  • Pseudorandomness for Regular Branching Programs via Fourier Analysis
    Omer Reingold, Thomas Steinke and Salil Vadhan.

Accepted papers in Approx - Papers

  • Improved Hardness of Approximating Chromatic Number
    Sangxia Huang

  • Sketching Earth-Mover Distance on Graph Metrics
    Andrew McGregor and Daniel Stubbs

  • Online Square-into-Square Packing
    Sandor Fekete and Hella-Franziska Hoffmann

  • Scheduling Subset Tests: One-time, Continuous, and How They Relate
    Edith Cohen, Haim Kaplan and Yishay Mansour

  • Partial Interval Set Cover Trade-offs Between Scalability and Optimality
    Katherine Edwards, William Kennedy and Simon Griffiths

  • 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

  • Spectral Sparsification in Dynamic Graph Streams
    Kook Jin Ahn, Sudipto Guha and Andrew McGregor

  • Capacitated Network Design on Undirected Graphs
    Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li and Srivatsan Narayanan

  • 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

  • A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
    Shayan Oveis Gharan and Luca Trevisan

  • 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

  • Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback
    Sudipto Guha and Kamesh Munagala

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

  • Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
    Kyle Fox, Sungjin Im, Janardhan Kulkarni and Benjamin Moseley

  • Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems
    Pierre Fraigniaud, Magnus M. Halldorsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosen

  • A local computation approximation scheme to maximum matching
    Yishay Mansour and Shai Vardi

  • Multiple Traveling Salesmen in Asymmetric Metrics
    Zachary Friggstad

  • The Online Stochastic Generalized Assignment Problem
    Saeed Alaei, Mohammadtaghi Hajiaghayi and Vahid Liaghat

  • Interdiction Problems on Planar Graphs
    Feng Pan and Aaron Schild

  • Online Multidimensional Load Balancing
    Adam Meyerson, Alan Roytman and Brian Tagiku

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Eugenio Noto