Introduction
This special issue of the journal Theory of Computing presents expanded and refined versions of the most significant research from the 2012 co-located workshops: the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 16th International Workshop on Randomization and Computation (RANDOM). Guest edited by Alexandr Andoni and Atri Rudra, this collection represents the pinnacle of theoretical research in approximation and randomness from that year.
Bridging the Gap: From Workshop to Journal
In theoretical computer science, the rapid dissemination of ideas often occurs through workshop "extended abstracts." While these abstracts allow for the quick sharing of new results, they frequently lack the comprehensive proofs and meticulous polish required for a permanent scholarly record. This special issue addresses this gap by providing a venue for the most impactful work to undergo a second, even more rigorous, peer-review process. The goal is to ensure that these high-impact contributions meet the high standards of a permanent journal record.
The Selection Process
The journey from submission to journal publication was highly selective. The initial pool consisted of 137 submissions across both workshops. The program committees first selected 56 papers (28 from each workshop) for presentation at the events held at the Massachusetts Institute of Technology.
From this subset, the guest editors invited only nine papers to contribute to this special issue. These invited works were expanded by their authors to include full technical details and then subjected to the standard rigorous refereeing process of Theory of Computing. Ultimately, eight papers successfully met these high standards, representing approximately 6% of the original workshop submissions. The breakdown of the selection process was as follows:
- APPROX 2012: 70 submissions $\rightarrow$ 28 accepted $\rightarrow$ 5 invited to the special issue.
- RANDOM 2012: 67 submissions $\rightarrow$ 28 accepted $\rightarrow$ 4 invited to the special issue.
Core Research Pillars
The papers included in this issue span four fundamental pillars of modern theoretical computer science, reflecting the deep mathematical synergy between approximation (finding "good enough" solutions to hard problems) and randomness (using stochastic processes to solve problems more efficiently):
- Approximation Algorithms: Developing methods to find near-optimal solutions for computationally difficult (NP-hard) problems.
- Hardness of Approximation: Establishing mathematical limits on how closely certain problems can be approximated, providing a boundary for algorithmic efficiency.
- Pseudorandomness: The construction of deterministic structures that mimic the properties of random ones, a crucial tool in derandomization.
- Property Testing: The study of algorithms that can determine if a large object possesses a specific property by examining only a tiny, randomly selected portion of it.
Conclusion
The 2012 APPROX and RANDOM workshops, and the subsequent journal issue, were made possible by the dedicated work of the program committees, which included researchers from leading institutions such as Microsoft Research, MIT, Carnegie Mellon, and IBM. This collection stands as a testament to the vibrancy and depth of the fields of approximation and randomization, providing a rigorous foundation for future work in these sub-fields.
Summary updated