Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PIOTR FALISZEWSKI:
All reports by Author Piotr Faliszewski:

TR04-064 | 25th June 2004
Piotr Faliszewski

Exponential time reductions and sparse languages in NEXP

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



ISSN 1433-8092 | Imprint