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

摘要

The quantified derandomization problem of a circuit class with a function B : N N is the following: Given an input circuit 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 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 . 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.