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.

A group of $n$ users want to run a distributed protocol $π$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $π$, is able to maliciously flip bits on the channels. Can we efficiently simulate $π$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $π$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $π$ that 1) fails with probability at most $δ$, for any $δ>0$; and 2) sends $\tilde{O}(L + T)$ bits, where the $\tilde{O}$ notation hides a $\log (nL/ δ)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $α$ is not constant. In particular, we give an algorithm that sends $O( L (1 + (1/α) \log (n L/δ) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $α$. We note that if $α$ is $Ω\left( \log (n L/δ) \right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal.

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, showing that they require linear space to guarantee a better-than-2 approximation [50, 52]. This result relies on a lower bound for the cycle-finding problem, showing that it is hard for a one-pass streaming algorithm to find a cycle in a union of matchings. The end-goal of our research is to prove a similar lower bound for multi-pass streaming algorithms that guarantee a better-than-2 approximation for Max-Cut, a highly challenging open problem. In this paper, we take a significant step in this direction, showing that even o(log n)-pass streaming algorithms need nΩ(1) space to solve the cycle-finding problem. Our proof is quite involved, dividing the cycles in the graph into “short” and “long” cycles, and using tailor-made lower bound techniques to handle each case.

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.

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.

For a directed graph G with n vertices and a start vertex u_start, we wish to (approximately) sample an L-step random walk over G starting from u_start with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ̃(n ⋅ L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ̃(n ⋅ √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω̃(n ⋅ L^{1/p}) space. In addition, we show a similar Θ̃(n ⋅ √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph.

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 a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? Assuming there are no malicious parties, Gallager gave an 𝒪(n log log n)-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties. We present a novel n ⋅ 𝒪̃(√{log n})-round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map "close" messages to "close" codewords, while messages that are not close are mapped to codewords that are very far apart. We view our result as a first step towards a theory of property preserving interactive coding, i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager’s, preserves this property of the original protocol.

We give an almost quadratic n2−o(1) lower bound on the space consumption of any o(√logn)-pass streaming algorithm solving the (directed) s-t reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including maximum matching, shortest path, matrix rank, and linear programming.

In the geometric transportation problem, we are given a collection of points $P$ in $d$-dimensional Euclidean space, and each point is given a supply of $μ(p)$ units of mass, where $μ(p)$ could be a positive or a negative integer, and the total sum of the supplies is $0$. The goal is to find a flow (called a transportation map) that transports $μ(p)$ units from any point $p$ with $μ(p) > 0$, and transports $-μ(p)$ units into any point $p$ with $μ(p) < 0$. Moreover, the flow should minimize the total distance traveled by the transported mass. The optimal value is known as the transportation cost, or the Earth Mover's Distance (from the points with positive supply to those with negative supply). This problem has been widely studied in many fields of computer science: from theoretical work in computational geometry, to applications in computer vision, graphics, and machine learning. In this work we study approximation algorithms for the geometric transportation problem. We give an algorithm which, for any fixed dimension $d$, finds a $(1+\varepsilon)$-approximate transportation map in time nearly-linear in $n$, and polynomial in $\varepsilon^{-1}$ and in the logarithm of the total supply. This is the first approximation scheme for the problem whose running time depends on $n$ as $n\cdot \mathrm{polylog}(n)$. Our techniques combine the generalized preconditioning framework of Sherman, which is grounded in continuous optimization, with simple geometric arguments to first reduce the problem to a minimum cost flow problem on a sparse graph, and then to design a good preconditioner for this latter problem.