License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.645
URN: urn:nbn:de:0030-drops-53285
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5328/
Go to the corresponding LIPIcs Volume Portal

Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

Tighter Connections between Derandomization and Circuit Lower Bounds

pdf-format:
38.pdf (0.5 MB)

Abstract

We tighten the connections between circuit lower bounds and derandomization for each of the following three types of derandomization:
- general derandomization of promiseBPP (connected to Boolean circuits),
- derandomization of Polynomial Identity Testing (PIT) over fixed finite fields (connected to arithmetic circuit lower bounds over the same field), and
- derandomization of PIT over the integers (connected to arithmetic circuit lower bounds over the integers).

We show how to make these connections uniform equivalences, although at the expense of using somewhat less common versions of complexity classes and for a less studied notion of inclusion.

Our main results are as follows:
1. We give the first proof that a non-trivial (nondeterministic subexponential-time) algorithm for PIT over a fixed finite field yields arithmetic circuit lower bounds.
2. We get a similar result for the case of PIT over the integers, strengthening a result of Jansen and Santhanam [JS12] (by removing the need for advice).
3. We derive a Boolean circuit lower bound for NEXP intersect coNEXP from the assumption of sufficiently strong non-deterministic derandomization of promiseBPP (without advice), as well as from the assumed existence of an NP-computable non-empty property of Boolean functions useful for proving superpolynomial circuit lower bounds (in the sense of natural proofs of [RR97]); this strengthens the related results of [IKW02].
4. Finally, we turn all of these implications into equivalences for appropriately defined promise classes and for a notion of robust inclusion/separation (inspired by [FS11]) that lies between the classical "almost everywhere" and "infinitely often" notions.

BibTeX - Entry

@InProceedings{carmosino_et_al:LIPIcs:2015:5328,
  author =	{Marco L. Carmosino and Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova},
  title =	{{Tighter Connections between Derandomization and Circuit Lower Bounds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{645--658},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5328},
  URN =		{urn:nbn:de:0030-drops-53285},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.645},
  annote =	{Keywords: derandomization, circuit lower bounds, polynomial identity testing, promise BPP, hardness vs. randomness}
}

Keywords: derandomization, circuit lower bounds, polynomial identity testing, promise BPP, hardness vs. randomness
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI