Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMBINATORIAL NULLSTELLENSATZ:
Reports tagged with Combinatorial Nullstellensatz:
TR26-193 | 18th September 2026
Mika Göös, Kaave Hosseini, Valentin Imbach, Anastasia Sofronova

Algebraic Complexity Approach to Sign-Rank

An outstanding open problem asks if there exists a boolean matrix with unbounded sign-rank, but bounded randomised communication complexity. We make progress towards this question by proving lower bounds against real linear sketches (a model weaker than sign-rank): Alice and Bob send few linear measurements to a referee, who makes ... more >>>




ISSN 1433-8092 | Imprint