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.

Accepter Papers
Accepted papers in Random - Papers

  • A Combination of Testability and Decodability by Tensor Products-Michael Viderman
  • Rainbow Connectivity of Random Sparse Graphs-Alan Frieze and Charalampos E. Tsourakakis
  • Almost k-wise vs. k-wise Independent Permutations, and Uniformity for General Group Actions-Noga Alon and Shachar Lovett
  • Extractors for Turing-machine Sources-Emanuele Viola
  • Two-Sided Error Proximity Oblivious Testing-Oded Goldreich and Igor Shinkar
  • On the Coin Weighing Problem with the Presence of Noise-Nader H. Bshouty
  • Limitations of Local Filters of Lipschitz and Monotone Functions-Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova
  • Tight Bounds on the Threshold for Permuted k-colorability-Varsha Dani and Cristopher Moore and Anna Olson
  • Maximal Empty Boxes Amidst Random Points-Adrian Dumitrescu and Minghui Jiang
  • Extractors for Polynomial Sources over Constant-Size Fields of Small Characteristic-Eli Ben-Sasson and Ariel Gabizon
  • A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller Codes-Noga Ron-Zewi and Madhu Sudan
  • A Discrepancy Lower Bound for Information Complexity-Mark Braverman and Omri Weinstein
  • Analysis of k-means++ for Separable Data-Ragesh Jaiswal and Nitin Garg
  • Pseudorandomness for Linear Length Branching Programs and Stack Machines-Andrej Bogdanov and Periklis A. Papakonstantinou and Andrew Wan
  • Tight Bounds for Testing k-Linearity-Eric Blais and Daniel Kane
  • Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors-Ariel Gabizon and Ronen Shaltiel
  • Finding Small Sparse Cuts Locally by Random Walk-Tsz Chiu Kwok and Lap Chi Lau
  • A Sharper Local Lemma with Improved Applications-Kashyap Kolipaka and Mario Szegedy and Yixin Xu
  • On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation-Jelani Nelson and Huy L. Nguyen and David P. Woodruff
  • Multiple-choice Balanced Allocation in (almost) Parallel-Petra Berenbrink and Artur Czumaj and Matthias Englert and Tom Friedetzky and Lars Nagel
  • Spectral Norm of Symmetric Functions -Anil Ada and Omar Fawzi and Hamed Hatami
  • An Explicit VC-Theorem for Low-Degree Polynomials -Eshan Chattopadhyay and Adam Klivans and Pravesh Kothari
  • Mirror Descent based Interactive Database Privacy -Prateek Jain and Abhradeep Thakurta
  • Optimal Hitting Sets for Combinatorial Shapes -Aditya Bhaskara and Devendra Desai and Srikanth Srinivasan
  • Testing Lipschitz Functions on Hypergrid Domains -Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova
  • 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

Accepted papers in Approx - Papers

  • Approximating Bounded Occurrence Ordering CSPs-Venkatesan Guruswami and Yuan Zhou
  • Approximating Minimum-Cost Connected $T$-joins-Joseph Cheriyan and Zachary Friggstad and Zhihan Gao
  • On the NP-hardness of Max-Not-2-Johan Hastad
  • Improved Inapproximability for TSP-Michael Lampis
  • New and Improved Bounds for the Minimum Set Cover Problem-Rishi Saket and Maxim Sviridenko
  • Additive Approximation for Near-Perfect Phylogeny Construction-Pranjal Awasthi and Avrim Blum and Jamie Morgenstern and Or Sheffet
  • Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply-Parinya Chalermsook and Julia Chuzhoy and Sampath Kannan and Sanjeev Khanna
  • Approximation Algorithms for Generalized and Variable-sized Bin Covering-Matthias Hellwig and Alexander Souza
  • iBGP and Constrained Connectivity-Michael Dinitz and Gordon Wilfong
  • The Remote Set Problem on Lattices-Ishay Haviv
  • Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues-Suguru Tamaki and Yuichi Yoshida
  • 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
  • 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
  • Improved Spectral-Norm Bounds for Clustering-Pranjal Awasthi and Or Sheffet
  • Maximum Matching in Semi-Streaming with Few Passes-Christian Konrad and Frédéric Magniez and Claire Mathieu
  • Hardness of Vertex Deletion and Project Scheduling-Ola Svensson
  • Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems-Per Austrin and Toniann Pitassi and Yu Wu
  • 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
  • Prize-collecting Survivable Network Design in Node-weighted Graphs-Chandra Chekuri and Alina Ene and Ali Vakilian
  • New Approximation Results for Resource Replication Problems-Samir Khuller and Barna Saha and Kanthi K. Sarpatwar
  • The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover-Dana Moshkovitz
  • Approximating Minimum Linear Ordering Problems-Satoru Iwata and Prasad Tetali and Pushkar Tripathi
  • Planarizing an Unknown Surface-Yury Makarychev and Anastasios Sidiropoulos
  • Approximation Algorithm for Non-Boolean MAX k-CSP-Konstantin Makarychev and Yury Makarychev
  • 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
  • Primal-dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs-Piotr Berman and Grigory Yaroslavtsev