Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR26-183 | 16th September 2026
Emanuele Viola

Nilpotency determines multiparty communication complexity

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

TR26-182 | 16th September 2026
Manon Blanc, Prateek Dwivedi, Nutan Limaye, Meena Mahajan, Magnus Rahbek Dalgaard Hansen

Tight Lower Bounds for Algebraic Communication and Applications

Revisions: 1

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


TR26-181 | 15th September 2026
Vinayak Kumar, Geoffrey Mon

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

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



previous PreviousNext next


ISSN 1433-8092 | Imprint