All reports by Author Bernhard Haeupler:

__
TR22-146
| 9th November 2022
__

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai#### Interactive Coding with Small Memory

__
TR22-050
| 12th April 2022
__

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena#### Circuits Resilient to Short-Circuit Errors

__
TR19-153
| 6th November 2019
__

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi#### Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

__
TR18-032
| 14th February 2018
__

Gil Cohen, Bernhard Haeupler, Leonard Schulman#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Revisions: 1

__
TR16-090
| 27th May 2016
__

Bernhard Haeupler, Ameya Velingker#### Bridging the Capacity Gap Between Interactive and One-Way Communication

__
TR15-197
| 7th December 2015
__

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Constant-rate coding for multiparty interactive communication is impossible

__
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

__
TR15-014
| 18th January 2015
__

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Reliable Communication over Highly Connected Noisy Networks

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>>

Gil Cohen, Bernhard Haeupler, Leonard Schulman

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

Bernhard Haeupler, Ameya Velingker

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

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

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

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

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

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

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