Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Thomas Holenstein:

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

TR12-173 | 8th December 2012
Kfir Barhum, Thomas Holenstein

A Cookbook for Black-Box Separations and a Recipe for UOWHFs

We present a new framework for proving fully black-box
separations and lower bounds. We prove a general theorem that facilitates
the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box
construction does ... more >>>

TR09-129 | 30th November 2009
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

TR04-102 | 20th October 2004
Thomas Holenstein

Key Agreement from Weak Bit Agreement

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

ISSN 1433-8092 | Imprint