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

In the mid 1980's, Yao presented a constant-round protocol for
securely computing any two-party functionality in the presence of
semi-honest adversaries (FOCS 1986). In this paper, we provide a
complete description of Yao's protocol, along with a rigorous
proof of security. Despite the importance of Yao's protocol to the
field ... more >>>

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>