All reports by Author Klim Efremenko:

__
TR23-187
| 27th November 2023
__

Klim Efremenko, Michal Garlik, Dmitry Itsykson#### Lower bounds for regular resolution over parities

__
TR23-066
| 4th May 2023
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Protecting Single-Hop Radio Networks from Message Drops

__
TR22-179
| 16th December 2022
__

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Round-vs-Resilience Tradeoffs for Binary Feedback Channels

__
TR22-174
| 23rd November 2022
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Revisions: 2

__
TR22-146
| 9th November 2022
__

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

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

__
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

__
TR21-160
| 15th November 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Tight Bounds for General Computation in Noisy Broadcast Networks

__
TR21-060
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Optimal Error Resilience of Adaptive Message Exchange

__
TR21-051
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

__
TR19-132
| 26th September 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Radio Network Coding Requires Logarithmic Overhead

Revisions: 1

__
TR19-111
| 16th August 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Noisy Beeps

__
TR18-054
| 24th March 2018
__

Klim Efremenko, Elad Haramaty, Yael Kalai#### Interactive Coding with Constant Round and Communication Blowup

Revisions: 1

__
TR17-162
| 26th October 2017
__

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson#### Barriers for Rank Methods in Arithmetic Complexity

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

__
TR16-086
| 29th May 2016
__

Noga Alon, Klim Efremenko, Benny Sudakov#### Testing Equality in Communication Graphs

Revisions: 1

__
TR15-197
| 7th December 2015
__

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

__
TR15-014
| 18th January 2015
__

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

__
TR14-007
| 17th January 2014
__

Mark Braverman, Klim Efremenko#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

__
TR11-154
| 17th November 2011
__

Klim Efremenko#### From Irreducible Representations to Locally Decodable Codes

__
TR10-134
| 23rd August 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

__
TR10-047
| 23rd March 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### Local list decoding with a constant number of queries

Revisions: 1

__
TR08-069
| 5th August 2008
__

Klim Efremenko#### 3-Query Locally Decodable Codes of Subexponential Length

Klim Efremenko, Michal Garlik, Dmitry Itsykson

The proof system resolution over parities (Res($\oplus$)) operates with disjunctions of linear equations (linear clauses) over $\mathbb{F}_2$; it extends the resolution proof system by incorporating linear algebra over $\mathbb{F}_2$. Over the years, several exponential lower bounds on the size of tree-like Res($\oplus$) refutations have been established. However, proving a superpolynomial ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

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, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... 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 >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. What is the largest fraction of corruptions that ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either `beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

Klim Efremenko, Elad Haramaty, Yael Kalai

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>>

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>

Noga Alon, Klim Efremenko, Benny Sudakov

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose

that on each vertex of the graph there is a player having an $n$-bit

string. Each player is allowed to communicate with its neighbors according

to an agreed communication protocol, and the players must decide,

deterministically, if their inputs ...
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 >>>

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

Mark Braverman, Klim Efremenko

In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient

to a noise rate of up to $1/2-\varepsilon$, ...
more >>>

Klim Efremenko

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially

corrupted.

In this paper we ... more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.

Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors

to a locally decodable code that can recover from a much higher error-rate. We also show how to ...
more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Recently Efremenko showed locally-decodable codes of sub-exponential

length. That result showed that these codes can handle up to

$\frac{1}{3} $ fraction of errors. In this paper we show that the

same codes can be locally unique-decoded from error rate

$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from

error rate $1-\alpha$ ...
more >>>

Klim Efremenko

Locally Decodable Codes (LDC) allow one to decode any particular

symbol of the input message by making a constant number of queries

to a codeword, even if a constant fraction of the codeword is

damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a

$3$-query LDC with sub-exponential length of size

$\exp(\exp(O(\frac{\log ...
more >>>