**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

# Uniform Derandomization from Pathetic Lower Bounds

## 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**: Uniform Derandomization from Pathetic Lower Bounds

**Author(s)**: Eric Allender, Fengming Wang

**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, nearly cubic lower bounds for formula size, nearly n loglog n size lower bounds for branching programs, n^1+cd for depth d threshold circuits). Here, we present two instances where ``pathetic'' lower bounds of the form n^1+epsilon would suffice to derandomize interesting classes of probabilistic algorithms. We show: If the word problem over S5 requires constant-depth threshold circuits of size n^1+epsilon for some epsilon > 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 there are no constant-depth arithmetic circuits of size n^1+epsilon for the problem of multiplying 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).

**Subject**: unspecified

**Area**: Other

**Language**: English

**Year**: 2010

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

**Journal**: Electronic Colloquium on Computational Complexity

**Volume**: 69

**Issue**: 69

**Url**: http://www.eccc.uni-trier.de/report/2010/069/

### 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**