Tell, Roei
Improved Bounds for Quantified Derandomization of ConstantDepth Circuits and Polynomials
Abstract
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 cal{C} and a parameter B=B(n), given a circuit C in cal{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 constantdepth 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 currentlyknown 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 constantdepth 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 depth3 circuit that they left as an open problem. We also consider the question of constructing hittingset 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.
BibTeX  Entry
@InProceedings{tell:LIPIcs:2017:7534,
author = {Roei Tell},
title = {{Improved Bounds for Quantified Derandomization of ConstantDepth Circuits and Polynomials}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {13:113:48},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7534},
URN = {urn:nbn:de:0030drops75349},
doi = {10.4230/LIPIcs.CCC.2017.13},
annote = {Keywords: Computational complexity, derandomization, quantified derandomization, hittingset generator, constantdepth circuits}
}
01.08.2017
Keywords: 

Computational complexity, derandomization, quantified derandomization, hittingset generator, constantdepth circuits 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

01.08.2017 