This collection contains the expanded and fully refereed versions of selected papers presented at the 22nd International Conference on Randomization and Computation (RANDOM 2018). The conference was held at Princeton University, August 20-22, 2018, in a meeting held jointly with APPROX 2018. The proceedings of this joint meeting was published in the Dagstuhl LIPIcs series. The RANDOM portion of the proceedings featured 30 accepted papers, chosen by the program committee from a total of 73 submissions.

After discussion with the RANDOM PC (chaired by Eric Blais, and of which I was a member), two papers were invited to the special issue. These papers were refereed to the usual rigorous standards of Theory of Computing. Short summaries of these articles are as follows.

• “Sunflowers and Robust Sunflowers from Randomness Extractors” by Xin Li, Shachar Lovett, and Jiapeng Zheng

  In this paper the authors provide a new approach to the classic Erdős-Rado Sunflower Conjecture in extremal combinatorics. They show that the existence of randomness extractors with appropriate properties for certain structured randomness sources can be used to infer the existence of sunflowers in large set systems. (The target sources are the so-called “block min-entropy” sources, which were previously used in a related way for obtaining “lifting theorems” in communication complexity by Göös et al.)

  This new connection provides sunflowers which “scale” with the quantitative strength of the available extractors, and the authors exhibit extractors sufficient to essentially match previous results on this problem; the connection is also shown to apply to the so-called “robust sunflowers” introduced by Rossman—which, like sunflowers, have found uses in the theory of computation.

  This paper helped motivate the subsequent breakthrough on the Sunflower Conjecture by Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang (STOC'20).

• “Round Complexity Versus Randomness Complexity in Interactive Proofs” by Maya Leshkowitz

  Interactive Proofs are protocols for conversation between a computationally powerful, but untrusted Prover and a skeptical, polynomial-time Verifier with a source of random bits. This work shows the surprising result that Interactive Proofs can always be made to have a number of rounds of interaction noticeably smaller than their total randomness usage. The author gives a general and interesting transformation of $r(n)$-random-bit protocols into equivalent $O(r(n)/\log n)$-round protocols. In this transformation, the new Prover repeatedly provides, not one, but many possible continuations of the old, simulated protocol; the new Verifier critically inspects these continuations with an eye toward both their probabilistic mass and their consistency properties, before choosing one to drive the simulation forward.

My thanks to the authors for their contributions, and to the anonymous referees for their valuable assistance. It was my pleasure to be involved in the preparation of this Special Issue for Theory of Computing.

RANDOM 2018 Program Committee

Eric Blais (chair) (U. Waterloo)
Joshua Brody (Swarthmore College)
Xi Chen (Columbia U.)
Gil Cohen (Princeton and Tel Aviv U.)
Andrew Drucker (U. Chicago)
Tom Gur (UC Berkeley)
Daniel Kane (UC San Diego)
Pravesh Kothari (Princeton U. and IAS)
Reut Levi (Weizmann Institute)
Aleksandar Nikolov (U. Toronto)
Lev Reyzin (U. Illinois Chicago)
Noga Ron-Zewi (U. Haifa)
Ron Rosenthal (Technion)
Atri Rudra (U. Buffalo)
Or Sheffet (U. Alberta)
Thomas Watson (U. Memphis)
Yuichi Yoshida (NII, Tokyo)