Uniform derandomization from pathetic lower bounds

Eric Allender, V. Arvind, Fengming Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

A recurring theme in the literature on derandomization is that probabilistic algorithms can be simulated quickly by deterministic algorithms, if one can obtain impressive (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is needed for derandomization, existing lower bounds seem rather pathetic (linear-size lower bounds for general circuits [30], nearly cubic lower bounds for formula size [23], nearly nloglogn size lower bounds for branching programs [12], n 1+cd for depth d threshold circuits [26]). Here, we present two instances where "pathetic" lower bounds of the form n 1+ε would suffice to derandomize interesting classes of probabilistic algorithms. We show: - If the word problem over S5 requires constant-depth threshold circuits of size n1+ε for some ε>0, then any language accepted by uniform polynomial-size probabilistic threshold circuits can be solved in subexponential time (and more strongly, can be accepted by a uniform family of deterministic constant-depth threshold circuits of subexponential size.) - If no constant-depth arithmetic circuits of size n1+ε can multiply a sequence of n 3-by-3 matrices, then for every constant d, black-box identity testing for depth-d arithmetic circuits with bounded individual degree can be performed in subexponential time (and even by a uniform family of deterministic constant-depth AC0 circuits of subexponential size).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages380-393
Number of pages14
DOIs
StatePublished - 2010
Event13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain
Duration: Sep 1 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6302 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
CountrySpain
CityBarcelona
Period9/1/109/3/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Circuit Complexity
  • Derandomization
  • Polynomial Identity Testing

Fingerprint Dive into the research topics of 'Uniform derandomization from pathetic lower bounds'. Together they form a unique fingerprint.

Cite this