Braverman, Rao, Raz, and Yehudayoff (SICOMP 2014) showed that there is an explicit pseudorandom generator (PRG) that fools standard-order regular read-once branching programs (ROBPs) with seed length
$$
O(\log n \cdot \log \log n + \log n \cdot \log(wd/\epsilon)),
$$
where $w$ is the width of ... more >>>

In this paper we show that iterated multiplication over a group has constant-communication protocols if and only if the
group is nilpotent, thus giving a new characterization of nilpotency based on communication
complexity.

more >>>

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and ... more >>>