Group:Algorithms, Complexity and Cryptography Group
Title: Uniform Derandomization from Pathetic Lower Bounds
Speaker: Eric Allender Rutgers, the State University of NJ
Time: 2011-10-14 13:30-2011-10-14 15:00
Venue: FIT 1-222

Abstract:

 

 

It's long been known that derandomization follows from strong lower bounds; the contribution of this paper is to show that derandomization also sometimes follows from very weak (even "pathetic") lower bounds.

 

The problem of multiplying a sequence of 3-by-3 matrices is complete for Arithmetic NC^1. If this problem can be shown to require constant-depth arithmetic circuits of size at least $n^{1+\epsilon}$ for some $\epsilon > 0$, then for every $d$, black-box identity testing for depth $d$ arithmetic circuits can be performed in subexponential time.

 

Related results also hold in the setting of Boolean circuit complexity. �If the word problem over S_5 (a standard complete problem for NC^1) requires TC^0 circuits of size at least $n^{1+\epsilon}$, then probabilistic TC^0 has uniform deterministic circuits of subexponential size.

 

This is joint work with V. Arvind, Rahul Santhanam, and Fengming Wang. A preliminary version of the paper may be found here:http://ftp.cs.rutgers.edu/pub/allender/pathetic.pdf



Short Bio:

Eric Allender is a well-known researcher in the field of computational complexity, and has given numerous plenary addresses internationally at symposia on theoretical computer science.  He received a B.A. from the University of Iowa in 1979, majoring in Computer Science and Theatre, and a Ph.D. from Georgia Tech in 1985.  He has been at Rutgers University since then, serving as department chair from 2006 to 2009.  He is a Fellow of the ACM, and serves on the editorial boards of ACM Transactions on Computation Theory, Computational Complexity, and The Chicago Journal of Theoretical Computer Science.  He has chaired the Conference Committee for the annual IEEE Conference on Computational Complexity, and he serves on the Scientific Board for the Electronic Colloquium on Computational Complexity (ECCC). is a well-known researcher in the field of computational complexity, and has given numerous plenary addresses internationally at symposia on theoretical computer science.  He received a B.A. from the University of Iowa in 1979, majoring in Computer Science and Theatre, and a Ph.D. from Georgia Tech in 1985.  He has been at Rutgers University since then, serving as department chair from 2006 to 2009.  He is a Fellow of the ACM, and serves on the editorial boards of ACM Transactions on Computation Theory, Computational Complexity, and The Chicago Journal of Theoretical Computer Science.  He has chaired the Conference Committee for the annual IEEE Conference on Computational Complexity, and he serves on the Scientific Board for the Electronic Colloquium on Computational Complexity (ECCC).