In the content-oblivious model, communication is limited to sending content-less pulses over asynchronous channels. Despite this extreme restriction, Censor-Hillel et al. (Dist. Comp., 2023) showed that any computation can be simulated on 2-edge-connected graphs, assuming a designated leader. Subsequent work investigated the necessity of this assumption. Frei et al. (DISC 2024, Dist. Comp. 2026) and Chalopin et al. (DISC 2025) designed content-oblivious leader-election algorithms for rings, thereby eliminating the need for an initial leader. Non-uniform leader election is possible on 2-edge-connected graphs (Chalopin et al., DISC 2025).

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity $$O(n \cdot \textsf{ID}_{\max })$$ , where $$\textsf{ID}_{\max }$$ is the maximal assigned ID. As it turns out, this dependency on $$\textsf{ID}_{\max }$$ is inherent: we show a lower bound of $$\Omega (n \log {\textsf{ID}_{\max }})$$ messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings. Here, however, the algorithm does not terminate but only quiescently stabilizes: all nodes eventually settle on an internal decision and stop receiving messages. Preliminary versions of parts of this research have appeared at the conferences PODC 2024 as a brief announcement and at DISC 2024 as a full paper.

Interactive coding allows two parties to conduct a distributed computation despite noise corrupting a certain fraction of their communication. Dani et al. (Inf. and Comp., 2018) suggested a novel setting in which the amount of noise is unbounded and can significantly exceed the length of the (noise-free) computation. While no solution is possible in the worst case, under the restriction of oblivious noise, Dani et al. designed a coding scheme that succeeds with a polynomially small failure probability. We revisit the question of conducting computations under this harsh type of noise and devise a computationally-efficient coding scheme that guarantees the success of the computation, except with an exponentially small probability. This higher degree of correctness matches the case of coding schemes with a bounded fraction of noise. Our simulation of an N-bit noise-free computation in the presence of T corruptions, communicates an optimal number of O(N+T) bits and succeeds with probability 1-2^(-Ω(N)). We design this coding scheme by introducing an intermediary noise model, where an oblivious adversary can choose the locations of corruptions in a worst-case manner, but the effect of each corruption is random: the noise either flips the transmission with some probability or otherwise erases it. This randomized abstraction turns out to be instrumental in achieving an optimal coding scheme.

We revisit the fundamental question of information exchange between$n$parties connected by a noisy binary broadcast channel, where the noise affects the transmitter (EI-Gamal, 1987). That is, a bit transmitted by a party is flipped with some fixed probability, and all parties receive the same (possibly flipped) bit. We provide matching upper and lower bounds for the omniscience task where each party starts with a single bit and wants to learn the input bit of all other parties. We show that Θ (log$n$) rounds of communication are necessary and sufficient for solving this task with 0(1) error probability. This proves an exponential gap between our case, where the noise affects the transmitter, and the case previously studied in the literature, where the noise affects each receiver independently. In that case, Θ (log log$n$) rounds are necessary and sufficient to achieve omniscience (Gallager, 1988; Goyal, Kindler, Saks, 2008). We complement our results by proving that computing the parity of all input bits also requires$O(\log n)$rounds of communication, implying again an exponential gap between the two settings. We further extend our positive result to computing any interactive protocol π that assumes a (noiseless) broadcast channel. Via a simple coding technique we show that a multiplicative overhead of$O(\log n)$rounds with respect to the noiseless case is sufficient to reliably compute π with o(1) error probability over a noisy broadcast channel, with noise at the transmitter.

We analyze resilient protocols over noisy networks, focusing on the interesting setting where$n$computing parties (clients) are supported by a set of$k$assisting servers. All communication links suffer from random noise, and the goal is to design noise-resilient computations with low round-complexity compared to the noiseless case. We give tight bounds for the case where a constant number of servers is present. We show that$\Theta(\log n)$rounds are necessary and sufficient to compute any non-constant function of the clients' inputs, with error probability tending to 0. We further show a lower bound of$\Omega(\log n/k)$rounds, for networks with$k < O(\log n)$servers. This lower bound suggests that additional assisting servers could help reducing the overall round complexity.

We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation.

International audience

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n*ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on $ID_max$ is inherent: we show a lower bound of Omega(n*log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence.

We examine sorting algorithms for $n$ elements whose basic operation is comparing $t$ elements simultaneously (a $t$-comparator). We focus on algorithms that use only a single round or two rounds -- comparisons performed in the second round depend on the outcomes of the first round comparators. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for $n=t^{2^k}$ with any $k\ge 1$ and a variety of possible values of $t$. For some values of $t$, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other $n$ and $t$), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-rounds sorting algorithm for any $n$ and $t$. Our algorithm uses an asymptotically optimal number of $O(\max(\frac{n^{3/2}}{t^2},\frac{n}{t}))$ comparators, with high probability, i.e., with probability at least $1-1/n$. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.

Broadcasting and gossiping are fundamental communication tasks in networks. In broadcasting,one node of a network has a message that must be learned by all other nodes. In gossiping, every node has a (possibly different) message, and all messages must be learned by all nodes. We study these well-researched tasks in a very weak communication model, called the {\em beeping model}. Communication proceeds in synchronous rounds. In each round, a node can either listen, i.e., stay silent, or beep, i.e., emit a signal. A node hears a beep in a round, if it listens in this round and if one or more adjacent nodes beep in this round. All nodes have different labels from the set $\{0,\dots , L-1\}$. Our aim is to provide fast deterministic algorithms for broadcasting and gossiping in the beeping model. Let $N$ be an upper bound on the size of the network and $D$ its diameter. Let $m$ be the size of the message in broadcasting, and $M$ an upper bound on the size of all input messages in gossiping. For the task of broadcasting we give an algorithm working in time $O(D+m)$ for arbitrary networks, which is optimal. For the task of gossiping we give an algorithm working in time $O(N(M+D\log L))$ for arbitrary networks. At the time of writing this paper we were unaware of the paper: A. Czumaj, P. Davis, Communicating with Beeps, arxiv:1505.06107 [cs.DC] which contains the same results for broadcasting and a stronger upper bound for gossiping in a slightly different model.

We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible.

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction of 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists corruptions in up to a fraction of 1/5 of the transmissions in each direction of the interactive channel . We further show that such a level of noise is maximal for coding schemes whose communication blowup is sub-exponential. Our coding scheme has taken a surprising inspiration from Blockchain technology.

Interactive coding allows two or more parties to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work (the second part) we provide computationally efficient, constant rate schemes that conduct any computation on arbitrary networks, and succeed with high probability in the presence of adversarial noise that can insert, delete, or alter communicated messages. Our schemes are non-fully-utilized and incur a polynomial (in the size of the network) blowup in the round complexity. Our first scheme resists an oblivious adversary that corrupts at most a fraction$\frac { \varepsilon }{m}$of the total communication, where$m$is the number of links in the network and$\varepsilon $is a small constant. In contrast to the first part of this work, the scheme in this part does not assume that the parties pre-share a long random string. Our second scheme resistsan arbitrary(non-oblivious) adversary that corrupts at most a fraction$\frac { \varepsilon }{m\log m}$of the communication. We further improve the resilience to$\vphantom {\sum ^{R}}\frac { \varepsilon }{m\log \log m}$by assuming the parties pre-share a long common random$\vphantom {\sum ^{R}}$string.

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. In a nutshell, this approach consists of capturing all the possible states of a distributed system at a certain time as a simplicial complex called protocol complex, and viewing computation as a simplicial map from that complex to the so-called output complex, that captures all possible legal output states of the system.

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide an efficient, constant rate scheme that conducts any computation on any arbitrary network, and succeeds with high probability as long as an oblivious adversary corrupts at most \frac εm fraction of the total communication, where m is the number of links in the network and ε is a small constant. In this work (the first part), our scheme assumes that the parties share a random string to which the adversarial noise is oblivious. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.

We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems.

We consider the task of communicating an (infinite) data stream in the sliding window model, where communication takes place over a noisy channel with an adversarial substitution noise rate up to 1. Specifically, for any noise level ${p<1}$ and any small $\varepsilon>0$, we design an efficient coding scheme, such that as long as the effective noise level in the sliding window is below $p$, the receiver decodes at least a $(1-p-\varepsilon)$-prefix of the current window. We prove that it is impossible to decode more than a $(1-p)$-prefix of the window in the worst case, which makes our scheme optimal in this sense. Our scheme runs in polylogarithmic time in the size of the window (per transmitted element), causes constant communication overhead, and succeeds with overwhelming probability. The scheme assumes the parties preshare a long random string unknown to the channel. When the noisy channel is additive, we lift the shared randomness assumption and design a scheme that is resilient to levels of noise below $p<1/2$.

We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties. We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases $T$ transmissions, the coding scheme will take $N+2T$ transmissions using an alphabet of size $4$ (alternatively, using $2N+4T$ transmissions over a binary channel) to correctly simulate any binary protocol that takes $N$ transmissions assuming a noiseless channel. We can further reduce the communication to $N+T$ by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme. Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures $T$.

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate).

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 communication is noisy, while maintaining a constant asymptotic rate , i.e., while keeping \(\liminf _{n,R\rightarrow \infty } R/R'\) positive. Rajagopalan and Schulman (STOC ’94) were the first to consider this question, and provided a coding scheme with rate \(O(1/\log (d+1))\) , where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is \(O(1/\log n)\) , which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a ( d -regular) network has mixing time m , then there exists an efficient coding scheme with rate \(O(1/m^3\log m)\) . This implies a constant rate coding scheme for any n -party protocol over a d -regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees \(n^{\varOmega (1)}\) .

Multiparty interactive coding allows a network of n parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC 1994) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of O(log(A + 1)) for networks whose topology has a maximal degree Δ. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send. We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman et al. (J. ACM 2018) to show that if the network's topology is a cycle, then there is a specific cycle task for which any coding scheme has a communication blowup of Q(log n). This is quite surprising since the cycle has a maximal degree of Δ = 2, implying a coding with a constant blowup when all parties are forced to speak at all rounds. We complement our lower bound with a matching coding scheme for the cycle task that has a communication blowup of θ(log n). This makes our lower bound for the cycle task tight.

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network. Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.

We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability ϵ, our coding scheme achieves a communication rate of 1- O(√/H(ϵ)), together with negligible exp(-Ω(ϵ4n/logn)) failure probability (over the randomness of the channel). A rate of 1 - Θ(√/H(ϵ)) is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)].

We consider interactive communication performed over two types of noisy channels: binary error channels with noiseless feedback and binary erasure channels. In both cases, the noise model is adversarial. Assuming at most $\varepsilon$-fraction of the bits can be corrupted, we show coding schemes that simulate any alternating interactive protocol with rate $1-\Theta(H(\varepsilon))$. All our simulations are simple, randomized, and computationally efficient. The rates of our coding schemes stand in contrast to the interactive communication rates supported by random or adversarial error channels without feedback, for which the best known coding schemes achieve rates of $1-\Theta(\sqrt{\varepsilon})$ and $1-\Theta(\sqrt{\varepsilon \log \log 1/\varepsilon})$, respectively. As these rates are conjectured to be optimal, our result implies a large asymptotic gap between interactive communication rates over noisy channels with and without feedback. Such a gap has no equivalent in the standard one-way communication setting.

We consider the question of interactive communication, in which two remote parties perform a computation, while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties “out of sync,” so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and tolerates noise rates of up to 1/18 - ε. To this end, we develop a novel primitive we name edit-distance tree code. The edit-distance tree code is carefully designed to replace the Hamming distance constraints in Schulman's tree codes (IEEE Trans. Inf. Theory, 1996), with a stronger edit-distance requirement.

How much adversarial noise can protocols for interactive communication tolerate? This question was examined by Braverman and Rao (IEEE Trans. Inf. Theory, 2014) for the case of “robust” protocols, where each party sends messages only in fixed and predetermined rounds. We consider a new class of protocols for interactive communication, which we call adaptive protocols. Such protocols adapt structurally to the noise induced by the channel in the sense that both the order of speaking, and the length of the protocol may vary depending on observed noise. We define models that capture adaptive protocols and study upper and lower bounds on the permissible noise rate in these models. When the length of the protocol may adaptively change according to the noise, we demonstrate a protocol that tolerates noise rates up to 1/3. When the order of speaking may adaptively change as well, we demonstrate a protocol that tolerates noise rates up to 2/3. Hence, adaptivity circumvents an impossibility result of 1/4 on the fraction of tolerable noise (Braverman and Rao, 2014).

We study 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 ∊ < 1/2, our coding scheme achieves a communication rate of and a failure probability of exp(−n/log n) in length n protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from 1. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i.e., of the form exp(− logO(1) n) (Braverman, ITCS 2012). For channels in which an adversary controls the noise pattern our coding scheme can tolerate Ω(1/log n) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encodable and decodable systematic tree code of length n that has relative distance Ω(1/log n) and rate approaching 1, defined over an O(log n)-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate in the random error model, and approaching rate 1 in the adversarial error model.

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.

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any nonadaptive protocol can withstand is 1/3. In addition, we provide a simple and efficient nonadaptive coding scheme that succeeds as long as the fraction of noise is at most 1/3 - ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a coding scheme that withstands the optimal tolerable erasure rate of 1/2 - ε [Franklin et al., IEEE Trans. Info. Theory, 2015], but operates in a much simpler and more efficient way than the previous schemes. Our coding scheme works with an alphabet of size 4, in contrast to prior schemes in which the alphabet size grows as ε → 0. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1/3 - ε.

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any robust protocol can resist is 1/3. Additionally, we provide a simple and efficient robust protocol that succeeds as long as the fraction of noise is at most 1/3--ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet.

We consider interactive communication performed over two simple types of noisy channels: binary error channels with noiseless feedback and binary erasure channels. In both cases, the noise model is adversarial Assuming at most ε-fraction of the bits can be corrupted, we show coding schemes that simulate any alternating interactive protocol with rate 1 — Θ(H(ε)). All our simulations are simple, randomized, and computationally efficient. The rates of our coding schemes stand in contrast to the interactive communication rates supported by random or adversarial error channels without feedback, for which the best known coding schemes achieve rates of and , respectively. As these rates are conjectured to be optimal, our result implies a large asymptotic gap between interactive communication rate over noisy channels with and without feedback. Such a gap has no equivalent in the standard one-way communication setting.

We consider the task of communicating a data stream-a long, possibly infinite message not known in advance to the sender-over a channel with adversarial noise. For any given noise rate c1/2.

Consider two parties, Alice and Bob, who hold private inputs x and y, and wish to compute a function f (x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f (x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f (x, y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties' inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and errorresilience are contradictory goals. In particular, we show that for every constant c > 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.

Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors.

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems $A$ and $B$ of a (possibly) unknown quantum state $|\psi\rangle \in {\cal H}_A \otimes {\cal H}_B$. Their goal is to calculate and share a new state $|\varphi\rangle = U|\psi\rangle$, where $U$ is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state $|\varphi'\rangle$ that coincides with $|\varphi\rangle = U|\psi\rangle$ up to local operations on $A$ and on $B$, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

We revisit the problem of reliable interactive communication over a noisy channel and obtain the first fully (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memoryless noisy channel with constant capacity and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman (1993), our simulation uses a tree-code, yet as opposed to the nonefficient construction of absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an efficient emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore, we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memory less noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman [Schulman 1993] our simulation uses a tree-code, yet as opposed to the non-constructive absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an explicit emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.