Klim Efremenko

FOCS Conference 2025 Conference Paper

Constant Rate Codes for Adaptive Broadcasts Do Not Exist

• Klim Efremenko
• Gillat Kol
• Dmitry Paramonov
• Raghuvansh R. Saxena

Can the n-party broadcast channel, where any symbol sent by one party is received by all, be made resilient to noise with low overhead? Namely, is it possible to construct interactive error-correcting codes that convert any protocol designed for the noiseless broadcast channel into one that works over the noisy broadcast channel and is not much longer than the original protocol? [12, STOC 2018] showed that such interactive codes with constant multiplicative overhead are possible under the assumption that the noiseless protocol being simulated is non-adaptive, meaning that it is restricted to have a pre-determined order of turns. Their noise resilient simulating protocols, however, require adaptivity, where each party can decide whether or not to broadcast given all the information available to them, including their input and received transcript. The question of whether such a simulation is possible for general, potentially adaptive, noiseless protocols was left open. We resolve this question negatively, proving that any interactive code that converts adaptive noiseless broadcast protocols into adaptive broadcast protocols resilient to stochastic errors must incur a multiplicative overhead of Ω(log n/ log log n), which is nearly tight.

STOC Conference 2024 Conference Paper

Lower Bounds for Regular Resolution over Parities

• Klim Efremenko
• Michal Garlík
• Dmitry Itsykson

The proof system resolution over parities (Res(⊕)) operates with disjunctions of linear equations (linear clauses) over GF(2); it extends the resolution proof system by incorporating linear algebra over GF(2). Over the years, several exponential lower bounds on the size of tree-like refutations have been established. However, proving a superpolynomial lower bound on the size of dag-like Res(⊕) refutations remains a highly challenging open question. We prove an exponential lower bound for regular Res(⊕). Regular Res(⊕) is a subsystem of dag-like Res(⊕) that naturally extends regular resolution. This is the first known superpolynomial lower bound for a fragment of dag-like Res(⊕) which is exponentially stronger than tree-like Res(⊕). In the regular regime, resolving linear clauses C 1 and C 2 on a linear form f is permitted only if, for both i ∈ {1,2}, the linear form f does not lie within the linear span of all linear forms that were used in resolution rules during the derivation of C i . Namely, we show that the size of any regular Res(⊕) refutation of the binary pigeonhole principle BPHP n n +1 is at least 2 Ω(∛ n /log n ) . A corollary of our result is an exponential lower bound on the size of a strongly read-once linear branching program solving a search problem. This resolves an open question raised by Gryaznov, Pudlak, and Talebanfard (CCC 2022). As a byproduct of our technique, we prove that the size of any tree-like Res(⊕) refutation of the weak binary pigeonhole principle BPHP n m is at least 2 Ω( n ) using Prover-Delayer games. We also give a direct proof of a width lower bound: we show that any dag-like Res(⊕) refutation of BPHP n m contains a linear clause C with Ω( n ) linearly independent equations.

SODA Conference 2023 Conference Paper

Interactive Coding with Small Memory

• Klim Efremenko
• Bernhard Haeupler
• Yael Tauman Kalai
• Gillat Kol
• Nicolas Resch
• Raghuvansh R. Saxena

In this work, we design an interactive coding scheme that converts any two party interactive protocol Π into another interactive protocol Π', such that even if errors are introduced during the execution of Π', the parties are able to determine what the outcome of running Π would be in an error-free setting. Importantly, our scheme preserves the space complexity of the protocol, in addition to the communication and computational complexities. Specifically, if the protocol Π has communication complexity T, computational complexity t, and space complexity s, the resulting protocol Π' is resilient to a constant ε > 0 fraction of adversarial errors, and has communication complexity approaching T as ε approaches 0, computational complexity poly( t ), and space complexity 𝒪( s log T ). Prior to this work, all known interactive coding schemes required the parties to use at least Ω( T ) space, as the parties were required to remember the transcript of the conversation thus far, or considered weaker error models.

STOC Conference 2023 Conference Paper

The Rate of Interactive Codes Is Bounded Away from 1

• Klim Efremenko
• Gillat Kol
• Dmitry Paramonov
• Raghuvansh R. Saxena

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability ‍є>0 independently, with only a 1+ O (√(є)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as є goes to ‍0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as є goes to 0, but retaining the assumption that the noiseless protocol is alternating. In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking . In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than 1. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors ‍є > 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS ‍2014].

FOCS Conference 2022 Conference Paper

Binary Codes with Resilience Beyond 1/4 via Interaction

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. Saxena
• Zhijun Zhang 0007

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 codes is at most 1/2, reliable transmission is possible only if the channel corrupts (flips) at most a 1/4-fraction of the communicated bits. We revisit the reliable transmission problem in the two-way setting, where both Alice and Bob can send bits to each other. Our main result is the construction of two-way error correcting codes that are resilient to a constant fraction of corruptions strictly larger than 1/4. Moreover, our code has constant rate and requires Bob to only send one short message. We mention that our result resolves an open problem by Haeupler, Kamath, and Velingker [APPROX-RANDOM, 2015] and by Gupta, Kalai, and Zhang [STOC, 2022]. Curiously, our new two-way code requires a fresh perspective on classical error correcting codes: While classical codes have only one distance guarantee for all pairs of codewords (i. e. , the minimum distance), we construct codes where the distance between a pair of codewords depends on the “compatibility” of the messages they encode. We also prove that such codes are necessary for our result.

STOC Conference 2022 Conference Paper

Circuits resilient to short-circuit errors

• Klim Efremenko
• Bernhard Haeupler
• Yael Tauman Kalai
• Pritish Kamath
• Gillat Kol
• Nicolas Resch
• Raghuvansh R. 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. Can we design such a resilient circuit C ′ whose size is roughly comparable to that of C ? Prior work gave a positive answer for the special case where C is a formula.

STOC Conference 2021 Conference Paper

Optimal error resilience of adaptive message exchange

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. 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 allows the parties to exchange their inputs?

FOCS Conference 2021 Conference Paper

Statistically Near-Optimal Hypothesis Selection

• Olivier Bousquet
• Mark Braverman
• Gillat Kol
• Klim Efremenko
• Shay Moran

Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class $\mathcal{Q}=\{q_{1}, \ldots, q_{n}\}$ of distributions, and a sampling access to an unknown target distribution $p$, the goal is to output a distribution $q$ such that $\mathsf{TV}(p, q)$ is close to opt, where $\mathsf{opt}=\min\nolimits_{i}\{\mathsf{TV}(p, q_{i})\}$ and TV (. ,.) denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e. g. , in the charming book by Devroye and Lugosi '00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood. We derive an optimal 2-approximation learning strategy for the Hypothesis Selection problem, outputting $q$ such that, $\mathsf{TV}(p, q)\leq 2\cdot\text{opt}+\varepsilon$, with a (nearly) optimal sample complexity of $\tilde{O}(\log n/\varepsilon^{2})$. This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT ‘19) gave a learner achieving the optimal 2-approximation, but with an exponentially worse sample complexity of $\tilde{O}(\sqrt{n}/\varepsilon^{2. 5})$, and Yatracos (Annals of Statistics '85) gave a learner with optimal sample complexity of $O(\log n/\varepsilon^{2})$ but with a sub-optimal approximation factor of 3. We mention that many works in the Density Estimation (a. k. a. , Distribution Learning) literature use Hypothesis Selection as a black box subroutine. Our result therefore implies an improvement on the approximation factors obtained by these works, while keeping their sample complexity intact. For example, our result improves the approximation factor of the algorithm of Ashtiani, Ben-David, Harvey, Liaw, and Mehrabian (JACM '20) for agnostic learning of mixtures of gaussians from 9 to 6, while maintaining its nearly-tight sample complexity.

FOCS Conference 2021 Conference Paper

Tight Bounds for General Computation in Noisy Broadcast Networks

• Klim Efremenko
• Gillat Kol
• Dmitry Paramonov
• Raghuvansh R. Saxena

Let II 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 II as input and outputs a noise resilient protocol II’ that simulates II over the noisy broadcast channel, where each received symbol is flipped with a fixed constant probability, independently. What is the minimum overhead in the number of rounds that is incurred by any such simulation scheme? A classical result by Gallager from the 80's shows that non-interactive T-round protocols, where the bit communicated in every round is independent of the communication history, can be converted to noise resilient ones with only an $\mathrm{O}(\log\log T$ ) multiplicative overhead in the number of rounds. Can the same be proved for any protocol? Or, are there protocols whose simulation requires an $\Omega(\log T)$ overhead (which always suffices)? We answer both the above questions in the negative: We give a simulation scheme with an $\tilde{O}(\sqrt{\log T})$ overhead for every protocol and channel alphabet. We also prove an (almost) matching lower bound of $\Omega(\sqrt{\log T})$ on the overhead required to simulate the pointer chasing protocol with T = n and polynomial alphabet.

FOCS Conference 2020 Conference Paper

Binary Interactive Error Resilience Beyond ${{}^{1}}\! /\! _{8}$ (or why $({{}^{1}}\! /\! _{2})^{3} > {{}^{1}}\! /\! _{8})$

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. Saxena

Interactive error correcting codesInteractive 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 such codes can protect against? If the error-resilient protocol is allowed to communicate large (constant sized) symbols, Braverman and Rao (STOC, 2011) show that the maximum rate of corruptions that can be tolerated is 1 /4. They also give a binary interactive error correcting protocol that only communicates bits and is resilient to 1 /2 fraction of errors, but leave the optimality of this scheme as an open problem. We answer this question in the negative, breaking the 1 /8 barrier. Specifically, we give a binary interactive error correcting scheme that is resilient to 5 /39 > 1 /8 fraction of adversarial errors. Our scheme builds upon a novel construction of binary list-decodable interactive codes with small list size.

STOC Conference 2020 Conference Paper

Interactive error resilience beyond 2/7

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. Saxena

FOCS Conference 2019 Conference Paper

Radio Network Coding Requires Logarithmic Overhead

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. 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, meaning that it was the only neighbor broadcasting. While the (noiseless) radio network model received a lot of attention over the last few decades, the effect of noise on radio networks is still not well understood. In this paper, we take a step forward and show that making radio network protocols resilient to noise may require a substantial performance overhead. Specifically, we construct a multi-hop network and a communication protocol over this network that works in T rounds when there is no noise. We prove that any scheme that simulates our protocol and is resilient to stochastic noise, requires at least cT log(n) rounds, for some constant c. This stands in contrast to our previous result (STOC, 2018), showing that protocols over the single-hop (clique) network can be made noise resilient with only a constant overhead. Our result also settles a recent conjecture by Censor-Hillel, Haeupler, Hershkowitz, Zuzic (2018). We complement the above result by giving a scheme to simulate any protocol with a fixed order of transmissions with only an O(log (n)) overhead.

STOC Conference 2018 Conference Paper

Interactive coding over the noisy broadcast channel

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. 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 is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed?

STOC Conference 2016 Conference Paper

Constant-rate coding for multiparty interactive communication is impossible

• 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 ε. 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 main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n-parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1-o(1) must communicate at least Ω(T log n / log log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is Θ(log log n / log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

FOCS Conference 2014 Conference Paper

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

• 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 -- ε, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize the region RU of pairs (α β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-differentiable curve with infinitely many pieces. We show that outside this region, the rate must be exponential. This suggests that in some error regimes, list-decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α β) for which one-sided unique decoding is possible in a way that Alice will output the correct answer.

STOC Conference 2012 Conference Paper

From irreducible representations to locally decodable codes

• Klim Efremenko

A q-query Locally Decodable Code (LDC) is an error-correcting code that allows to read any particular symbol of the message by reading only q symbols of the codeword even if the codeword is adversary corrupted. In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (ρ, V) of G and q elements g 1 ,g 2 ,..., g q in G such that there exists a linear combination of matrices ρ(g i ) that is of rank one, then we can construct a q-query Locally Decodable Code C:V-> F G . We show the potential of this approach by constructing constant query LDCs of sub-exponential length matching the best known constructions.

I&C Journal 2012 Journal Article

Mismatch sampling

• Raphaël Clifford
• Klim Efremenko
• Benny Porat
• Ely Porat
• Amir Rothschild

We reconsider the well-known problem of pattern matching under the Hamming distance. Previous approaches have shown how to count the number of mismatches efficiently, especially when a bound is known for the maximum Hamming distance. Our interest is different in that we wish to collect a random sample of mismatches of fixed size at each position in the text. Given a pattern p of length m and a text t of length n, we show how to sample with high probability up to c mismatches from every alignment of p and t in O ( ( c + log n ) ( n + m log m ) log m ) time. Further, we guarantee that the mismatches are sampled uniformly and can therefore be seen as representative of the types of mismatches that occur.

I&C Journal 2011 Journal Article

A black box for online approximate pattern matching

• Raphaël Clifford
• Klim Efremenko
• Benny Porat
• Ely Porat

We present a deterministic black box solution for online approximate matching. Given a pattern of length m and a streaming text of length n that arrives one character at a time, the task is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. Our solution requires O ( Σ j = 1 log 2 m T ( n, 2 j - 1 ) / n ) time for each input character, where T ( n, m ) is the total running time of the best offline algorithm. The types of approximation that are supported include exact matching with wildcards, matching under the Hamming norm, approximating the Hamming norm, k-mismatch and numerical measures such as the L 2 and L 1 norms. For these examples, the resulting online algorithms take O ( log 2 m ), O ( m log m ), O ( log 2 m / ϵ 2 ), O ( k log k log m ), O ( log 2 m ) and O ( m log m ) time per character, respectively. The space overhead is linear in the pattern size, which we show is optimal for any deterministic algorithm.

FOCS Conference 2010 Conference Paper

Local List Decoding with a Constant Number of Queries

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

Efremenko showed locally-decodable codes of subexponential length that can handle close to 1/6 fraction of errors. In this paper we show that the same codes can be locally unique-decoded from error rate 1/2 - α for any α > 0 and locally list-decoded from error rate 1 - α for any α > 0, with only a constant number of queries and a constant alphabet size. This gives the first sub-exponential length codes that can be locally list-decoded with a constant number of queries.

STOC Conference 2009 Conference Paper

3-query locally decodable codes of subexponential length

• 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 a recent work [Yek08] Yekhanin constructs a 3-query LDC with sub-exponential length of size exp(exp(O((log n)/(log log n)))). However, this construction requires a conjecture that there are infinitely many Mersenne primes. In this paper we give the first unconditional constant query LDC construction with subexponantial codeword length. In addition our construction reduces codeword length. We give construction of 3-query LDC with codeword length exp(exp(O(√{log n log log n ))). Our construction could also be extended to higher number of queries. We give a 2 r -query LDC with length of exp(exp(O(☂[r] log n (log log n) r-1 ))).

SODA Conference 2009 Conference Paper

From coding theory to efficient pattern matching

• Raphaël Clifford
• Klim Efremenko
• Ely Porat
• Amir Rothschild

We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with Hamming distance at most k and also returns the location and identity of each mismatch. The algorithm we present is deterministic and runs in Õ( kn ) time, matching the best known randomised time complexity to within logarithmic factors. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.

SODA Conference 2008 Conference Paper

Approximating general metric distances between a pattern and a text

• Ely Porat
• Klim Efremenko