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)