pdf icon
Volume 9 (2013) Article 12 pp. 437-439
Guest Editors' Foreword

This collection comprises the fully refereed and expanded versions of selected papers presented at the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012) and the 16th International Workshop on Randomization and Computation (RANDOM 2012) held in Boston, Massachusetts, August 15 -- August 17, 2012. The selection was made by the program committees of the respective meetings (listed below). Preliminary versions of the papers were presented at the workshops and the extended abstracts appeared in the proceedings of the meetings published by Springer.

70 extended abstracts were submitted to APPROX 2012; of these, 28 were accepted, and 5 invited to this Special Issue. 67 extended abstracts were submitted to RANDOM 2012; of these, 28 were accepted, and 4 invited to this Special Issue. The authors of 8 out of the 9 selected papers accepted the invitation.

The papers selected from APPROX 2012 cover topics of approximation algorithms and hardness of approximation, while the papers selected from RANDOM 2012 cover topics in pseudorandomness and property testing. All papers were refereed in accordance with the usual rigorous standards of Theory of Computing.

We would like to thank the authors for their contributions and the anonymous referees for their hard work that helped improve the quality of this issue. We would also like to specially thank ToC editor Oded Regev for guiding us through the editorial process. It was a pleasure to edit this special issue for Theory of Computing.

May 25, 2013

Alexandr Andoni
Guest Editor
for APPROX 2012
Atri Rudra
Guest Editor
for RANDOM 2012



APPROX 2012 Program Committee

Alexandr Andoni (Microsoft Research SVC)
Yossi Azar (Tel-Aviv University)
Shuchi Chawla (University of Wisconsin - Madison)
Anupam Gupta (Carnegie Mellon University) (chair)
Sariel Har-Peled (University of Illinois at Urbana-Champaign)
Jochen Koenemann (University of Waterloo)
Amit Kumar (Indian Institute of Technology, Delhi)
Lap Chi Lau (The Chinese University of Hong Kong)
Konstantin Makarychev (IBM Watson)
Monaldo Mastrolilli (IDSIA)
Dana Moshkovitz (MIT)
Rene Sitters (Vrije Universiteit Amsterdam)
David Steurer (Microsoft Research and Cornell)
Kunal Talwar (Microsoft Research SVC)
Jan Vondrak (IBM Almaden)
Lisa Zhang (Alcatel-Lucent Bell Labs)


RANDOM 2012 Program Committee

Eli Ben-Sasson (Technion)
Andrej Bogdanov (Chinese University of Hong Kong)
Mark Braverman (Princeton)
Colin Cooper (King's College, London)
Tobias Friedrich (Saarland University / Max-Planck-Institut)
Tali Kaufman (Bar-Ilan University)
Raghu Meka (IAS)
Jelani Nelson (Harvard)
Ilan Newman (Haifa)
Ryan O'Donnell (CMU)
Konstantinos Panagiotou (Max-Planck-Institut)
Prasad Raghavendra (Georgia Tech)
Atri Rudra (SUNY Buffalo)
Rocco Servedio (Columbia) (chair)
Alistair Sinclair (UC Berkeley)
Emanuele Viola (Northeastern)




List of papers currently accepted for publication in the Special Issue

  • Almost $k$-wise vs. $k$-wise independent permutations, and uniformity for general group actions, by Noga Alon and Shachar Lovett
  • Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic, by Eli Ben-Sasson and Ariel Gabizon
  • Optimal Hitting Sets for Combinatorial Shapes, by Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan
  • Hardness of Vertex Deletion and Project Scheduling, by Ola Svensson
  • Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four, by Cenny Wenner
  • A new upper bound on the query complexity for testing generalized Reed-Muller codes, by Noga Ron-Zewi and Madhu Sudan

APPROX-RANDOM 2012 Special Issue Table of Contents (with links to the articles)


Download article from ToC site:
[PDF (111K)]    [PS (260K)]    [PS.GZ (116K)]
[Source ZIP]
Keywords: foreword, special issue, APPROX-RANDOM 2012
ACM Classification: G.3, F.2
AMS Classification: 68Q25

[Plain Text Abstract]