Both works refer to the framework of quantified derandomization, and specifically when applied to constant-depth circuit (of various types ranging from AC0 to TC0). A generic quantified derandomization problem is defined by specifying a class of circuits $\mathcal{C}$ and an upper-bound $B$ on the number of exceptional inputs, and given a circuit $C\in\mathcal{C}$ with $n$ input bits that accepts all but at most $B(n)$ of its inputs, the task is to find an input $x$ such that $C(x)=1$. In both cases, such derandomization is presented for a pair $(\mathcal{C},B)$ such that solving the quantified derandomization problem with somewhat larger $\mathcal{C}$ or $B$ implies solving the related standard derandomization problem (i.e., one that refers to $B(n) = 2^{n-1}$). Hence, solving the standard derandomization problem only requires a ``modest'' quantitive improvement of Roei's results.
Added comment (3-Dec-2017): A related work (also of Roei), titled A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization has just been posted. It explains the failure of the first work to obtain quantified derandomization that yields standard derandomization results in the nature (i.e., black-box-ness) of the techniques used.
This work studies the question of quantified derandomization, which was introduced by Goldreich and Wigderson (STOC 2014). The generic quantified derandomization problem is the following: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, given a circuit $C\in\mathcal{C}$ with $n$ input bits, decide whether $C$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs. In the current work we consider three settings for this question. In each setting, we bring closer the parameter setting for which we can unconditionally construct relatively fast quantified derandomization algorithms, and the "threshold" values (for the parameters) for which any quantified derandomization algorithm implies a similar algorithm for standard derandomization.
For constant-depth circuits, we construct an algorithm for quantified derandomization that works for a parameter $B(n)$ that is only slightly smaller than a "threshold" parameter, and is significantly faster than the best currently-known algorithms for standard derandomization. On the way to this result we establish a new derandomization of the switching lemma, which significantly improves on previous results when the width of the formula is small. For constant-depth circuits with parity gates, we lower a "threshold" of Goldreich and Wigderson from depth five to depth four, and construct algorithms for quantified derandomization of a remaining type of layered depth-3 circuit that they left as an open problem. We also consider the question of constructing hitting-set generators for multivariate polynomials over large fields that vanish rarely, and prove two lower bounds on the seed length of such generators.
Several of our proofs rely on an interesting technique, which we call the randomized tests technique. Intuitively, a standard technique to deterministically find a "good" object is to construct a simple deterministic test that decides the set of good objects, and then "fool" that test using a pseudorandom generator. We show that a similar approach works also if the simple deterministic test is replaced with a distribution over simple tests, and demonstrate the benefits in using a distribution instead of a single test.
See ECCC TR16-191.
One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for $TC^0$, the class of constant-depth, polynomial-size circuits with majority gates. Relying on the results of Williams (2013), an appealing approach to prove such lower bounds is to construct a non-trivial derandomization algorithm for $TC^0$. In this work we take a first step towards the latter goal, by proving the first positive results regarding the derandomization of $TC^0$ circuits of depth $d>2$.
Our first main result is a quantified derandomization algorithm for $TC^0$ circuits with a super-linear number of wires. Specifically, we construct an algorithm that gets as input a $TC^0$ circuit $C$ over $n$ input bits with depth $d$ and $n^{1+\exp(-d)}$ wires, runs in almost-polynomial-time, and distinguishes between the case that $C$ rejects at most $2^{n^{1-1/5d}}$ inputs and the case that $C$ accepts at most $2^{n^{1-1/5d}}$ inputs. In fact, our algorithm works even when the circuit $C$ is a linear threshold circuit, rather than just a $TC^0$ circuit (i.e., $C$ is a circuit with linear threshold gates, which are stronger than majority gates).
Our second main result is that even a modest improvement of our quantified derandomization algorithm would yield a non-trivial algorithm for standard derandomization of all of $TC^0$, and would consequently imply that $NEXP\not\subseteq TC^0$. Specifically, if there exists a quantified derandomization algorithm that gets as input a $TC^0$ circuit with depth $d$ and $n^{1+O(1/d)}$ wires (rather than $n^{1+\exp(-d)}$ wires), runs in time at most $2^{n^{\exp(-d)}}$, and distinguishes between the case that $C$ rejects at most $2^{n^{1-1/5d}}$ inputs and the case that $C$ accepts at most $2^{n^{1-1/5d}}$ inputs, then there exists an algorithm with running time $2^{n^{1-\Omega(1)}}$ for standard derandomization of $TC^0$.
See ECCC TR17-145.
The quantified derandomization problem of a circuit class $\mathcal{C}$ with a function $B:\mathbb{N}\rightarrow\mathbb{N}$ is the following: Given an input circuit $C\in\mathcal{C}$ over $n$ bits, deterministically distinguish between the case that $C$ accepts all but $B(n)$ of its inputs and the case that $C$ rejects all but $B(n)$ of its inputs. This generalizes the standard derandomization problem, which is the special case where $B(n)=2^n/3$.
A major goal of this framework is to serve as a stepping-stone on the way to standard derandomization. Specifically, we want to construct reductions of the standard derandomization problem of a class $\mathcal{C}$ to the quantified derandomization problem (e.g., using strong error-reduction), and to then construct an algorithm that solves the latter.
In this note we show that if both the reduction (from standard derandomization to quantified derandomization) and the algorithm (for quantified derandomization) are constructed using two specific natural techniques that only rely on black-box access to the input circuit $C$, then a naive combination of the two algorithms does not suffice to yield a standard derandomization of $\mathcal{C}$. That is, when using these two techniques, the parameter value $B(n)$ to which standard derandomization is reduced is necessarily larger than the value $B(n)$ that the quantified derandomization algorithm can handle.
See ECCC TR17-187.