**Reading**PAGE

### Peer Evaluation activity

Trusted by | 1 |

Downloads | 3 |

Views | 25 |

### Total impact ?

#### Send a

### Eric has...

Trusted | 2 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

### This was brought to you by:

# Followblock this user
Eric Allender
*Trusted member*

## Professor

Dept. of Computer Science, Rutgers University, Piscataway, NJ

# Amplifying lower bounds by means of self-reducibility

## Oh la la

Your session has expired but *don’t worry*, your message

has been saved.Please log in and we’ll bring you back

to this page. You’ll just need to click “Send”.

**Your evaluation**is of great value to our authors and readers. Many thanks for your time.

Your **mailing list** is currently empty.

It will build up as you send messages

and links to your peers.

__No one__besides you has access to this list.

Enter the e-mail addresses of your recipients in the box below.

__Note__: Peer Evaluation will NOT store these email addresses log inYour message has been sent.

### Description

New Full text for this article was not available? Send a request to the author(s).

**Title**: Amplifying lower bounds by means of self-reducibility

**Author(s)**: Eric Allender, Michal Koucký

**Abstract**: 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 n1+&epsis; for every &epsis;> 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 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC0 circuits of size n1+&epsis;d. If one were able to improve this lower bound to show that there is some constant &epsis;> 0 (independent of the depth d) such that every TC0 circuit family recognizing BFE has size at least n1+&epsis;, then it would follow that TC0 NC1. We show that proving lower bounds of the form n1+&epsis; is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC0, TC0 and NC1 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 TC0 and AC0[6] circuits of size n1+c for some constant c depending on d.

**Subject**: unspecified

**Area**: Other

**Language**: English

**Year**: 2010

Affiliations : |
Dept. of Computer Science, Rutgers University, Piscataway, NJ |

**Journal**: Journal of the ACM

**Volume**: 57

**Issue**: 3

**Publisher**: ACM

**Pages**: 1 - 36

**Url**: http://portal.acm.org/citation.cfm?doid=1706591.1706594

**Doi**: 10.1145/1706591.1706594

### Leave a comment

### This contribution has not been reviewed yet. review?

You may receive the Trusted member label after :

• Reviewing **10 uploads**, whatever the media type.

• Being trusted by **10 peers**.

• If you are blocked by **10 peers** the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

#### Please select an affiliation to sign your evaluation:

#### Please select an affiliation:

### Eric's * Peer Evaluation activity*

Trusted by | 1 |

- FHeribert Vollmer,
*Professor*, Leibniz Universität Hannover.

Downloads | 3 |

Views | 25 |

- 1On strong separations from AC^0
- 1P-uniform circuit complexity
- 1On TC 0 , AC 0 , and Arithmetic Circuits
- 1Rudimentary reductions revisited 1 Introduction 2 Preliminaries
- 1A Note on the Representational Incompatibility of Function Approximation and Factored Dynam- ics
- 1A Note on the Representational Incompatabilty of Function Approximation and Factored Dynamics.
- 1On the complexity of numerical analysis
- 1Arithmetic Complexity, Kleene Closure, and Formal Power Series
- 1The complexity of computing maximal word functions
- 1Bounded depth arithmetic circuits: Counting and closure
- 1A First-Order Isomorphism Theorem
- 1Circuit Complexity before the Dawn of the New Millennium
- 1When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity
- 1Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
- 1Randomness as Circuit Complexity ( and the Connection to Pseudorandomness )
- 1Cracks in the defenses: Scouting out approaches on circuit lower bounds
- 1Power from random strings
- 1The directed planar reachability problem
- 1A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics
- 1Uniform Derandomization from Pathetic Lower Bounds
- 1Circuit complexity before the dawn of the new millennium
- 1Arithmetic Circuits and Counting Complexity Classes
- 1Making computation count
- 1The complexity of satisfiability problems: Refining Schaefer's theorem☆
- 1Avoiding Simplicity is Complex

### Eric* has...*

Trusted | 2 |

- Moshe Vardi,
*Professor*. - Heribert Vollmer,
*Professor*.

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

## Full Text request

### Your request will be sent.

Please enter your email address to be notified

when this article becomes available

**Your email**