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

A celebrated 1976 theorem of Aumann asserts that honest, rational
Bayesian agents with common priors will never "agree to disagree": if
their opinions about any topic are common knowledge, then those
opinions must be equal. Economists have written numerous papers
examining the assumptions behind this theorem. But two key questions
more >>>