This collection comprises the fully refereed and expanded versions of selected papers presented at the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013) and the 17th International Workshop on Randomization and Computation (RANDOM 2013) held at UC Berkeley, CA, USA, August 21 -- August 23, 2013. 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.

The APPROX Program Committee selected 23 out of 46 submissions for presentation at the Workshop; of these, 3 were invited to this Special Issue. The RANDOM Program Committee selected 25 out of 52 submissions; of these, 3 were invited to this Special Issue. The authors of the six selected papers accepted the invitation.

The papers selected from APPROX 2013 cover topics of approximation algorithms and hardness of approximation, while the papers selected from RANDOM 2013 cover topics in differential privacy and learning, property testing, and random structures and processes. 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. It was a pleasure to edit this special issue for Theory of Computing.

APPROX 2013 Program Committee

Nikhil Bansal (Eindhoven University, The Netherlands)
Chandra Chekuri (University of Illinois, Urbana-Champaign, USA)
Eden Chlamtáč (Ben-Gurion University, Israel)
Nikhil Devanur (Microsoft Research, Redmond, USA)
Uriel Fiege (Weizmann Institute, Israel)
Claire Matheiu (Brown University, USA)
Ankur Moitra (Institute for Advanced Study, Princeton, USA)
Seffi Naor (Technion, Israel)
Yuval Rabani (Hebrew University, Israel)
Prasad Raghavendra (University of California, Berkeley, USA) (Chair)
Roy Schwartz (Microsoft Research, Redmond, USA)
Mohit Singh (Microsoft Research, Redmond, USA)
Ola Svennson (École Polytechnique Fédéral de Lausanne, Switzerland)
MohammadTaghi Hajiaghayi (University of Maryland, College Park, USA)
Madhur Tulsiani (Toyota Technological Institute - Chicago, USA)
Rico Zenklusen (John Hopkins University, USA)

RANDOM 2013 Program Committee

Amit Chakrabarti (Dartmouth College, USA)
Nikolaos Fountalakis (University of Birmingham, UK)
Ariel Gabizon (Technion, Israel)
Parikshit Gopalan (Microsoft Research, Silicon Valley, USA)
Dan Gutfreund (IBM Research, Haifa, Israel)
Prahladh Harsha (Tata Institute of Fundamental Research, India)
Thomas Hayes (University of New Mexico, USA)
Michael Krivelevich (Tel Aviv University, Israel)
Shachar Lovett (University of California - San Diego, USA)
Russell Martin (University of Liverpool, UK)
Dieter van Melkebeek (University of Wisconsin - Madison, USA)
Sofya Raskhodnikova (Pennsylvania State University, USA) (Chair)
Shubhangi Saraf (Rutgers University, USA)
Christian Sohler (TU Dortmund University, Germany)
David P. Woodruff (IBM Research, Almaden, USA)
Amir Yehudayoff (Technion, Israel)

List of papers currently accepted for publication in the Special Issue

• A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs, by Shayan Oveis Gharan and Luca Trevisan
• On the NP-Hardness of Ordering Constraint Satisfaction Problems, by Per Austrin, Rajsekar Manokaran, and Cenny Wenner
• Absolutely Sound Testing of Lifted Codes, by Noga Ron-Zewi, Elad Haramaty, and Madhu Sudan
• Private Learning and Sanitazation: Pure vs. Approximate Differential Privacy, by Amos Beimel, Kobbi Nissim, and Uri Stemmer
• Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration, by Emmanuel Abbe and Andrea Montanari

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