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

# Reducing the complexity of reductions

## 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**: Reducing the complexity of reductions

**Author(s)**: Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

**Abstract**: We build on the recent progress regarding isomorphisms of com- plete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a Gap Theorem, showing that all sets complete under AC0 reductions are in fact already complete under NC0 reduc- tions. The following questions were left open in that paper: 1. Does the gap between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under iso- morphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0 -computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 mod 2 reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomor- phic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non- uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)

**Subject**: unspecified

**Area**: Other

**Language**: English

**Year**: 1997

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

**Journal**: Proceedings of the twentyninth annual ACM symposium on Theory of

**Volume**: 10

**Issue**: 2

**Publisher**: ACM Press

**Pages**: 730-738

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

**Doi**: 10.1145/258533.258671

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