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.

The Special Issue was completed on June 9, 2015.

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)

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