Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-187 | 3rd December 2017 14:50

A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization


Authors: Roei Tell
Publication: 3rd December 2017 15:02
Downloads: 965


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.

ISSN 1433-8092 | Imprint