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

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$.

1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all ... more >>>