Piotr Faliszewski

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>Joshua Grochow

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