Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR08-038 | 26th October 2009 09:55

Amplifying Lower Bounds by Means of Self-Reducibility

RSS-Feed




Revision #2
Authors: Eric Allender, Michal Koucký
Accepted on: 26th October 2009 09:55
Downloads: 5113
Keywords: 


Abstract:

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 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 NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+\epsilon_d}. If one were able to improve this lower bound to show that there is some constant \epsilon>0 such that every TC^0 circuit family recognizing BFE has size n^{1+\epsilon}, then it would follow that TC^0 \not= \NC^1.

We also show that problems with small uniform constant-depth 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 TC^0 and AC^0[6] circuits of size n^{1+c} for some constant c depending on d.



Changes to previous version:

We have provided more background and definitions, and also give much more detail regarding the uniformity of our reductions. We also include a new observation: all problems in NC$^1$ have AC$^0[q]$ circuits of subexponential size, for any q with at least 2 distinct prime factors.


Revision #1 to TR08-038 | 2nd December 2008 00:00

Amplifying Lower Bounds by Means of Self-Reducibility





Revision #1
Authors: Eric Allender, Michal Koucký
Accepted on: 2nd December 2008 00:00
Downloads: 3674
Keywords: 


Abstract:

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+epsilon} for every epsilon > 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 NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+epsilon_d}. If one were able to improve this lower bound to show that there is some constant epsilon>0 such that every TC^0 circuit family recognizing BFE has size n^{1+epsilon}, then it would follow that TC^0 not= NC^1. We show that proving lower bounds of the form n^{1+epsilon} is not ruled out by the Natural Proof framework of Razborov and Rudich, and thence there is currently no known barrier for separating classes such as ACC^0, TC^0, and NC^1 via existing "natural" approaches to proving circuit lower bounds.

We also show that problems with small uniform constant-depth 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 TC^0 and AC^0[6] circuits of size n^{1+c} for some constant c depending on d.


Paper:

TR08-038 | 4th April 2008 00:00

Amplifying Lower Bounds by Means of Self-Reducibility





TR08-038
Authors: Eric Allender, Michal Koucky
Publication: 4th April 2008 16:26
Downloads: 4168
Keywords: 


Abstract:

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 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 NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+\epsilon_d}. If one were able to improve this lower bound to show that there is some constant \epsilon>0 such that every TC^0 circuit family recognizing BFE has size n^{1+\epsilon}, then it would follow that TC^0 \not= \NC^1.

We also show that problems with small uniform constant-depth 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 TC^0 and AC^0[6] circuits of size n^{1+c} for some constant c depending on d.



ISSN 1433-8092 | Imprint