The threshold degree of a Boolean function $f$ is the minimum degree of
a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969
monograph, Minsky and Papert constructed a polynomial-size constant-depth
$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ... more >>>

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

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