Program Committee


Alexandr Andoni
Yossi Azar
Shuchi Chawla
Anupam Gupta (chair)
Sariel Har-Peled
Jochen Koenemann
Amit Kumar
Lap Chi Lau
Konstantin Makarychev
Monaldo Mastrolilli
Dana Moshkovitz
Rene Sitters
David Steurer
Kunal Talwar
Jan Vondrak
Lisa Zhang


Eli Ben-Sasson
Andrej Bogdanov
Mark Braverman
Colin Cooper
Tobias Friedrich
Tali Kaufman
Raghu Meka
Jelani Nelson
Ilan Newman
Ryan O'Donnell
Konstantinos Panagiotou
Prasad Raghavendra
Atri Rudra
Rocco Servedio (chair)
Alistair Sinclair
Emanuele Viola

Program Chairs

Anupam Gupta,
Carnegie Mellon University

Rocco Servedio,
Columbia University

Workshop Chairs

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

Notification to authors
June 8, 2012

Camera ready
June 15, 2012

August 15-17, 2012
Call for papers
Thank you

The Random/Approx organization would like to thank Microsoft Research New England for their support.


    APPROX + RANDOM 2012 Program

    (download the program in PDF here)

      Wed August 15

      9:00-10:28 Session 1 (Approx)

    • Approximation Algorithms for Generalized and Variable-sized Bin Covering - Matthias Hellwig and Alexander Souza
    • Online Flow Time Scheduling in the Presence of Preemption Overhead - Ho-Leung Chan and Tak-Wah Lam and Rongbin Li
    • Online scheduling of jobs with fixed start times on related machines - Leah Epstein and Lukasz Jez and Jiri Sgall and Rob van Stee
    • Approximating Minimum Linear Ordering Problems - Satoru Iwata and Prasad Tetali and Pushkar Tripathi

    • 10:28-10:50 coffee break

      10:50-11:50 Invited talk
      Speaker: Julia Chuzhoy

      11:50-12:56 Session 2 (Random)

      Chair: Rocco Servedio

    • Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic - Eli Ben-Sasson and Ariel Gabizon
    • Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors - Ariel Gabizon and Ronen Shaltiel
    • Extractors for Turing-machine sources - Emanuele Viola

    • 12:56-14:30 lunch (on your own)

      14:30-16:20 Session 3 (Approx)

    • Approximating minimum-cost connected $T$-joins - Joseph Cheriyan and Zachary Friggstad and Zhihan Gao
    • Improved Inapproximability for TSP - Michael Lampis
    • Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply - Parinya Chalermsook and Julia Chuzhoy and Sampath Kannan and Sanjeev Khanna
    • Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems - Per Austrin and Toniann Pitassi and Yu Wu
    • New and Improved Bounds for the Minimum Set Cover Problem - Rishi Saket and Maxim Sviridenko

    • 16:20-16:45 coffee break

      16:45-18:57 Session 4 (Random)

    • Rainbow Connectivity of Random Sparse Graphs - Alan Frieze and Charalampos E. Tsourakakis
    • Tight bounds on the threshold for permuted k-colorability - Varsha Dani and Cristopher Moore and Anna Olson
    • Multiple-choice Balanced Allocation in (almost) Parallel - Petra Berenbrink and Artur Czumaj and Matthias Englert and Tom Friedetzky and Lars Nagel
    • Maximal empty boxes amidst random points - Adrian Dumitrescu and Minghui Jiang
    • Analysis of k-means++ for Separable Data - Ragesh Jaiswal and Nitin Garg
    • On the Coin Weighing Problem with the Presence of Noise - Nader H. Bshouty
    • 19:00 Welcome Reception

      Thurs August 16

      9:00-10:50 Session 5 (Approx)

    • A new point of NP-hardness for 2-to-1 Label Cover - Per Austrin and Ryan O'Donnell and John Wright
    • Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four - Cenny Wenner
    • On the NP-hardness of Max-Not-2 - Johan Hastad
    • The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover - Dana Moshkovitz
    • Hardness of Vertex Deletion and Project Scheduling - Ola Svensson

    • 10:50-11:15 coffee break

      11:15-13:05 Session 6 (Random)

    • Optimal Hitting Sets for Combinatorial Shapes - Aditya Bhaskara and Devendra Desai and Srikanth Srinivasan
    • Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions - Noga Alon and Shachar Lovett
    • Pseudorandomness for linear length branching programs and stack machines - Andrej Bogdanov and Periklis A. Papakonstantinou and Andrew Wan
    • An Explicit VC-Theorem for Low-Degree Polynomials - Eshan Chattopadhyay and Adam Klivans and Pravesh Kothari
    • A Sharper Local Lemma with Improved Applications - Kashyap Kolipaka and Mario Szegedy and Yixin Xu

    • 13:10-14:30 lunch (on your own)

      14:30-16:20 Session 7 (Approx)

    • Prize-collecting Survivable Network Design in Node-weighted Graphs - Chandra Chekuri and Alina Ene and Ali Vakilian
    • Primal-dual approximation algorithms for node-weighted network design in planar graphs Piotr Berman and Grigory Yaroslavtsev
    • A systematic approach to bound factor revealing LPs and its application to the Metric and Squared Metric Facility Location Problems - Cristina G. Fernandes and Luis A. A. Meira and Flavio K. Miyazawa and Lehilton L. C.Pedrosa
    • iBGP and Constrained Connectivity - Michael Dinitz and Gordon Wilfong
    • New Approximation Results for Resource Replication Problems - Samir Khuller and Barna Saha and Kanthi K. Sarpatwar

    • 16:20-16:45 coffee break

      16:45-18:35 Session 8 (Random)

    • Testing Lipschitz Functions on Hypergrid Domains - Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova.
    • Limitations of Local Filters of Lipschitz and Monotone Functions - Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova.
    • On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation - Jelani Nelson and Huy L. Nguyen and David P. Woodruff.
    • Two-Sided Error Proximity Oblivious Testing - Oded Goldreich and Igor Shinkar.
    • Tight Bounds for Testing k-Linearity - Eric Blais and Daniel Kane.

    • Fri August 17

      9:00-10:28 Session 9 (Random)

    • A Combination of Testability and Decodability by Tensor Products - Michael Viderman.
    • A new upper bound on the query complexity for testing generalized Reed-Muller codes - Noga Ron-Zewi and Madhu Sudan.
    • Mirror Descent based Interactive Database Privacy - Prateek Jain and Abhradeep Thakurta.
    • Finding Small Sparse Cuts Locally by Random Walk - Tsz Chiu Kwok and Lap Chi Lau.

    • 10:28-10:50 coffee break

      10:50-11:50 Invited talk
      Speaker: Yuval Peres

      11:50-12:56 Session 10 (Approx)

      Chair: Anupam Gupta

    • Approximation Algorithm for Non-Boolean MAX k-CSP - Konstantin Makarychev and Yury Makarychev
    • Approximating bounded occurrence ordering CSPs - Venkatesan Guruswami and Yuan Zhou
    • Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues - Suguru Tamaki and Yuichi Yoshida

    • 12:56-14:30 lunch (on your own)

      14:30-16:20 Session 11 (Random)

    • A discrepancy lower bound for information complexity - Mark Braverman and Omri Weinstein
    • Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming - Amit Chakrabarti and Ranganath Kondapally and Zhenghui Wang
    • Sparse and Lopsided Set Disjointness via Information Theory - Anirban Dasgupta and Ravi Kumar and D. Sivakumar
    • Downward Self-Reducibility of the Permanent - Revisited - Sanjeev Arora and Arnab Bhattacharyya and Rajsekar Manokaran and Sushant Sachdeva
    • Spectral Norm of Symmetric Functions - Anil Ada and Omar Fawzi and Hamed Hatami

    • 16:20-16:45 coffee break

      16:45-18:57 Session 12 (Approx)

    • Improved Spectral-Norm Bounds for Clustering - Pranjal Awasthi and Or Sheffet
    • Planarizing an unknown surface - Yury Makarychev and Anastasios Sidiropoulos
    • The Remote Set Problem on Lattices - Ishay Haviv
    • Maximum Matching in Semi-Streaming with Few Passes - Christian Konrad and Frederic Magniez and Claire Mathieu
    • What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid - Petros Boufounos and Volkan Cevher and Anna C. Gilbert and Yi Li and Martin J. Strauss
    • Additive Approximation for Near-Perfect Phylogeny Construction - Pranjal Awasthi and Avrim Blum and Jamie Morgenstern and Or Sheffet