# DIMACS Discrete Math/Theory of Computing Seminar

## Title:

An Isomorphism Theorem for Circuit Complexity

## Speaker:

- Eric Allender
- Rutgers University

## Place:

- CoRE Building, Room 431
- Busch Campus, Rutgers University

## Time:

- 4:30 pm
- Tuesday, February 13, 1996

## Abstract:

We show that all sets complete for NC^1 under AC^0 reductions are
isomorphic under AC^0-computable isomorphisms.
The question of whether or not all complete sets are isomorphic (known as
the "isomorphism question", or the "Berman-Hartmanis Conjecture") has been the
subject of a great deal of work in complexity theory. Lately, it has been
popular to conjecture that if f is a one-way function (i.e., a function that
is easy to compute but is hard to invert), then f(A) would NOT necessarily
be isomorphic to A. In this regard, it is interesting to note that, if
there are ANY one-way functions at all, then there are such functions in
AC^0. Thus our result shows that, for such a function f in AC^0, f(A)
IS isomorphic to A.

The proof technique relies on combinatorial notions from circuit complexity.
Our work also presents some interesting differences between uniform circuit
complexity and nonuniform circuit complexity: A key part of our proof
involves showing that the class of sets that are hard for NC^1 under AC^0
reductions are already hard under NC^0 reductions. We also show that this
is NOT true for dlogtime-uniform reductions.

This (informal) abstract avoids making precise certain notions regarding
"reductions" and "isomorphisms"; a detailed version of the paper is available
over the www at
http://www.cs.rutgers.edu/~allender/publications

(Joint work with Manindra Agrawal)

dimacs-www@dimacs.rutgers.edu
Document last modified on February 2, 1996