The log-rank conjecture and low degree polynomials

DOI10.1016/J.IPL.2003.09.020zbMath1183.68301OpenAlexW2046290908WikidataQ123197977 ScholiaQ123197977MaRDI QIDQ1029056

Paul Valiant

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.09.020

zbMATH Keywords

computational complexitycommunication complexityBoolean polynomialslog-rank conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On set intersection representations of graphs

Cites Work

• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Unnamed Item

This page was built for publication: The log-rank conjecture and low degree polynomials