We show that all sets complete for NC^1 under AC^0
reductions are isomorphic under AC^0-computable isomorphisms.

Although our proof does not generalize directly to other
complexity classes, we do show that, for all complexity classes C
closed under NC^1-computable many-one reductions, the sets ... more >>>

Mahaney's Theorem states that, assuming P \neq NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>