From the winner of the Turing Award and the Abel Prize, an introduction to computational
complexity theory, its connections and interactions with mathematics, and its central role in …

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 …

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 …

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 …

In the setting of error-correcting codes with feedback, Alice wishes to communicate ak-bit
message x to Bob by sending a sequence of bits over a channel while noiselessly receiving …

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 …

In interactive coding, Alice and Bob wish to compute some function f of their individual
private inputs x and y. They do this by engaging in a non-adaptive (fixed order, fixed length) …

We study coding schemes for multiparty interactive communication over synchronous
networks that suffer from stochastic noise, where each bit is independently flipped with …

Given a noiseless protocol π0 computing a function f (x, y) of Alice and Bob's private inputs
x, y, the goal of interactive coding is to construct an error-resilient protocol π computing f …

A cycle cover of a bridgeless graph G is a collection of simple cycles in G such that each
edge e appears on at least one cycle. The common objective in cycle cover computation is …