Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-193 | 18th September 2026 16:52

Algebraic Complexity Approach to Sign-Rank

RSS-Feed

Abstract:

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 a decision based on the evaluation of a low-degree polynomial. Our proof uses the Combinatorial Nullstellensatz and the rank method from algebraic circuit complexity.



ISSN 1433-8092 | Imprint