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

__
TR15-084
| 21st May 2015
__

Or Ordentlich, Ofer Shayevitz, Omri Weinstein#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

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

Or Ordentlich, Ofer Shayevitz, Omri Weinstein

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