## 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 S_{5} requires constant-depth threshold circuits of size n^{1+ε} 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 n^{1+ε} 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 AC^{0} circuits of subexponential size).

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings |

Pages | 380-393 |

Number of pages | 14 |

DOIs | |

State | Published - 2010 |

Event | 13th 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 2010 → Sep 3 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6302 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 |
---|---|

Country | Spain |

City | Barcelona |

Period | 9/1/10 → 9/3/10 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Keywords

- Circuit Complexity
- Derandomization
- Polynomial Identity Testing