Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ofer Shayevitz:

TR18-033 | 16th February 2018
Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

The Communication Complexity of Private Simultaneous Messages, Revisited

Revisions: 2

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the ... more >>>

TR15-084 | 21st May 2015
Or Ordentlich, Ofer Shayevitz, Omri Weinstein

Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... more >>>

ISSN 1433-8092 | Imprint