This collection comprises the expanded and fully refereed versions of selected papers presented at the 35th Computational Complexity Conference (CCC 2020), held July 2830, 2020, online. These papers were selected by the Program Committee from among the 36 papers that appeared in the conference proceedings. Preliminary versions of the papers were presented at the conference, and the extended abstracts appeared in the proceedings of the conference, published by Dagstuhl Publishing, LIPIcs.
The CCC Program Committee selected 36 out of 96 submissions for presentation at the conference; of these, the five described below were invited to this Special Issue. These five papers were refereed in accordance with the rigorous standards of Theory of Computing.
 “Sign rank vs. Discrepancy” by Kaave Hosseini, Hamed
Hatami and Shachar Lovett.
The main result of the paper is an optimal separation between the signrank of a matrix, which is the minimum rank of a matrix of the same sign pattern, and the discrepancy of a matrix, which is the maximal correlation it has with a rectangle. More specifically, the authors exhibit a matrix of signrank 3 and discrepancy $\exp(n)$. Prior to this work, the largest known separation was signrank $O(\log n)$ and discrepancy $\exp(n)$. The authors further observe that signrank of 3 is lowest possible, as any matrix of signrank 1 or 2 has discrepancy at least $1/{\mathrm{poly}}(n)$. As it is known that signrank characterizes the unboundederror randomized communication complexity model (i.e., error probability smaller than half), while discrepancy characterizes the weakly bounded error model (the communication cost includes a “penalty” depending on how close to half is the error probability), the result also implies an optimal separation between these classes. Moreover, by known relations between discrepancy and approximate rank, the above also gives an optimal separation between approximate and sign ranks.

“Hitting Sets Give TwoSided Derandomization of Small Space”
by Kuan Cheng and William Hoza.
Pseudorandom generators and hitting set generators naturally allow the derandomization of twosided and onesided error probabilistic algorithms, respectively. Motivated to derandomize smallspace computation and prove that $\BPL = \LL$ or $\RL = \LL$, researchers have been designing and analyzing pseudorandom generators (PRGs) and hitting set generators (HSGs) for the model of polynomialwidth readonce oblivious branching programs. Indeed, spaceefficient PRGs with logarithmic seed length for this model suffice to prove that $\BPL = \LL$, whereas the weaker objects, HSGs, suffice to prove the weaker result $\RL = \LL$. Both challenges remain elusive to date. The surprising result in this article is that hitting set generators with logarithmic seed length suffice for the derandomization of $\BPL$! The proof relies on the technique of local consistency: obtaining estimates for the probabilities that subcomputations yield specific values, and checking that these estimates are locally consistent. This whitebox reduction relies on the structure of the program. A second result gives a blackbox reduction that works with only query access to the program but relies on the program having only constantwidth. A third result shows that any generic reduction of the form “HSGs imply PRGs with similar parameters” would imply new unconditional PRGs and would put $\BPL$ in $\LL^{1+\varepsilon}$ for any constant $\varepsilon > 0$.
 “NonDisjoint Promise Problems from MetaComputational View of
Pseudorandom Generator Constructions” by Shuichi Hirahara.
Promise problems are relaxations of decision problems. To solve a promise problem, a device needs to output YES on a set $A$ of inputs and NO on another set $B$ of inputs. The device may answer arbitrarily on inputs outside $A \cup B$. Naturally, $A$ and $B$ are assumed to be disjoint, for if some string is both in $A$ and $B$, then no device can satisfy the above requirements. The paper introduces a new concept called “nondisjoint promise problems.” These are promise problems that under standard complexity assumptions would be nondisjoint and thus illdefined and cannot be solved by any device. For example, a wellknown complexity assumption, which suffices for constructing optimal pseudorandom generators, is that $E$, the class of problems solved in simply exponential time, requires exponential size circuits. Based on this assumption, no device can tell apart $A$, truthtables of functions in $E$, from $B$, truthtables of functions requiring circuitsize $2^{\Omega(n)}$ (since these sets of truthtables are not disjoint). Alas, settling whether $A$ and $B$ are disjoint is a longstanding open problem in computational complexity theory, perhaps beyond the reach of current techniques. The present paper shows that optimal hittingset generators (the onesided error analog of pseudorandom generators) could be attained even if $A$ and $B$ are disjoint, as long as it is computationally hard to tell $A$ and $B$ apart. This brings us closer to establishing derandomization since we can base it on weaker assumptions. In another setting, the computational hardness of supposedly nondisjoint promise problems would yield an equivalence between the worstcase hardness and averagecase hardness of $\PH$.
 “Multiparty KarchmerWigderson Games and Threshold Circuits”
by Alexander Kozachinskiy and Vladimir Podolskii.
KarchmerWigderson games are communication games whose communication complexity exactly captures the formula depth of the corresponding function. For a given Boolean function $f:\{0,1\}^n \to \{0,1\}$, Alice is given an input $x \in f^{1}(0)$ , Bob is given an input $y \in f^{1}(1)$ and their goal is to find a coordinate $i\in [n]$ on which $x_i$ and $y_i$ differ. Protocols for this game translate to De Morgan formulae computing $f$ with the same depth (and vice versa). This article generalizes the KarchmerWigderson framework to the numberinhand multiparty communication setting, where $k$ parties are given inputs, and they seek to find a coordinate on which all their inputs agree. For a certain class of functions (including the majority function), the communication cost of a protocol is shown to be equal up to a constant factor to the depth of a formula over the gate set consisting only of thresholds of arity $k+1$ (instead of AND, OR gates in De Morgan formulae). A beautiful application of this new perspective is an explicit construction of a logarithmicdepth formula, composed only of 3input majority gates, computing the majority function. An explicit logarithmicdepth formula computing the majority function with AND, OR gates follows from Ajtai, Komlós, and Szemerédi's seminal result. Valiant used the probabilistic method to give a simpler proof for the existence of such a formula. His proof was adapted by Goldreich to a probabilistic construction using only 3input majority gates, but the question of explicitness remained open. The present paper settles in the affirmative a conjecture by Cohen et al., who were motivated by applications in multiparty computation.
 “Connecting Perebor Conjectures: Towards a Search to
Decision Reduction for Minimizing Formulas”
by Rahul Ilango.
Whether the Minimum Circuit Size Problem, MCSP, is NPhard has been a central question in metacomplexity with farreaching consequences since the seminal work of Cook and Levin. The present paper focuses on a “cousin” of MCSP, called Minimum Formula Size Problem, or MFSP. If MFSP is NPhard, then it has a searchtodecision reduction. Thus, tackling the latter is a natural intermediate step before tackling the former. The present paper gives a $2^{O(N/\log\log N)}$ searchtodecision reduction that works for most inputs of length $N$, and a $2^{0.67 N}$ randomized reduction that works for all such inputs. The reductions rule out a “bizarre world” where finding the smallest formula of a given truth table requires brute force, but determining its size requires only polynomial time.
We would like to thank the authors for their contributions, the CCC Program Committee for their initial reviews, Shubhangi Saraf for her fantastic work as Chair of the Program Committee, László Babai for his advice on matters related to Theory of Computing, and the anonymous referees for their hard work. It was a pleasure to edit this Special Issue for Theory of Computing.
and
Avishay Tal
Guest Editors
CCC 2019 Program Committee
 Andrej Bogdanov (Chinese University of Hong Kong)
 Per Austrin (KTH Royal Institute of Technology)
 Zeev Dvir (Princeton University)
 Prahladh Harsha (Tata Institute of Fundamental Research)
 Toniann Pitassi (University of Toronto and IAS)
 Noga RonZewi (Haifa University)
 Shubhangi Saraf (Rutgers University) (Chair)
 Avishay Tal (University of California, Berkeley)
 Salil Vadhan (Harvard University)
 Ryan Williams (Massachusetts Institute of Technology)
 Ronald de Wolf (CWI and University of Amsterdam)
 Amir Yehudayoff (Technion—Israel Institute of Technology)
[About the Guest Editors]