Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Bernhard Haeupler:

TR18-032 | 14th February 2018
Gil Cohen, Bernhard Haeupler, Leonard Schulman

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

TR16-090 | 27th May 2016
Bernhard Haeupler, Ameya Velingker

Bridging the Capacity Gap Between Interactive and One-Way Communication

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

TR15-197 | 7th December 2015
Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Constant-rate coding for multiparty interactive communication is impossible

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our ... more >>>

TR15-165 | 14th October 2015
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.

For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>

TR15-014 | 18th January 2015
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Reliable Communication over Highly Connected Noisy Networks

We consider the task of multiparty computation performed over networks in
the presence of random noise. Given an $n$-party protocol that takes $R$
rounds assuming noiseless communication, the goal is to find a coding
scheme that takes $R'$ rounds and computes the same function with high
probability even when the ... more >>>

ISSN 1433-8092 | Imprint