TY - GEN

T1 - Amplifying lower bounds by means of self-reducibility

AU - Allender, Eric

AU - Koucký, Michal

PY - 2008

Y1 - 2008

N2 - We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n 1+ε for every ε > 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC0 circuits of size n 1+ε;d. If one were able to improve this lower bound to show that there is some constant ε > 0 such that every TC0 circuit family recognizing BFE has size n1+ε, then it would follow that TC0 ≠ NC1. We also show that problems with small uniform constantdepth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC0 and AC 0[6] circuits of size n1+ε for some constant c depending on d.

AB - We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n 1+ε for every ε > 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC0 circuits of size n 1+ε;d. If one were able to improve this lower bound to show that there is some constant ε > 0 such that every TC0 circuit family recognizing BFE has size n1+ε, then it would follow that TC0 ≠ NC1. We also show that problems with small uniform constantdepth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC0 and AC 0[6] circuits of size n1+ε for some constant c depending on d.

UR - http://www.scopus.com/inward/record.url?scp=51749115320&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51749115320&partnerID=8YFLogxK

U2 - 10.1109/CCC.2008.11

DO - 10.1109/CCC.2008.11

M3 - Conference contribution

AN - SCOPUS:51749115320

SN - 9780769531694

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 31

EP - 40

BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

Y2 - 23 June 2008 through 26 June 2008

ER -