Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rotem Oshman:

TR18-031 | 15th February 2018
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

TR15-002 | 2nd January 2015
Mark Braverman, Rotem Oshman

The Communication Complexity of Number-In-Hand Set Disjointness with No Promise

Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, $k$ players receive private inputs $X_1,\ldots,X_k\subseteq \{1,\ldots,n\}$, and their goal is to determine whether or not $\bigcap_{i = 1}^k X_i = \emptyset$. In this paper we prove a tight lower ... more >>>

ISSN 1433-8092 | Imprint