ECCC-Report TR16-191https://eccc.weizmann.ac.il/report/2016/191Comments and Revisions published for TR16-191en-usMon, 25 Feb 2019 14:46:46 +0200
Revision 3
| Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials |
Roei Tell
https://eccc.weizmann.ac.il/report/2016/191#revision3This 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.Mon, 25 Feb 2019 14:46:46 +0200https://eccc.weizmann.ac.il/report/2016/191#revision3
Revision 2
| Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials |
Roei Tell
https://eccc.weizmann.ac.il/report/2016/191#revision2This 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 {\bf 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 {\bf 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 {\bf 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.Sun, 14 May 2017 18:04:57 +0300https://eccc.weizmann.ac.il/report/2016/191#revision2
Revision 1
| Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials |
Roei Tell
https://eccc.weizmann.ac.il/report/2016/191#revision1This 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.Sun, 19 Feb 2017 14:06:01 +0200https://eccc.weizmann.ac.il/report/2016/191#revision1
Paper TR16-191
| Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials |
Roei Tell
https://eccc.weizmann.ac.il/report/2016/191Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.
In this work we make progress on several frontiers that they left open. Specifically, for constant-depth circuits, we construct an algorithm for quantified derandomization that is significantly faster than the best currently-known algorithms for standard derandomization, and works for a parameter $B(n)$ that is only slightly smaller than a ``barrier'' parameter that was shown by Goldreich and Wigderson. For constant-depth circuits with parity gates, we tighten a ``barrier'' 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 did not handle and left as an open problem (i.e., circuits with a top $\oplus$ gate, a middle layer of $\land$ gates, and a bottom layer of $\oplus$ gates).
In addition, we extend Goldreich and Wigderson's study of multivariate polynomials that vanish rarely to the setting of large finite fields. We prove two lower bounds on the seed length of hitting-set generators for polynomials over large fields that vanish rarely. As part of the proofs, we show a form of ``error reduction'' for polynomials (i.e., a reduction of the task of hitting arbitrary polynomials to the task of hitting polynomials that vanish rarely) that causes only a mild increase in the degree.Fri, 25 Nov 2016 11:11:35 +0200https://eccc.weizmann.ac.il/report/2016/191