Around the log-rank conjecture

Lee, T; Shraibman, A

Around the log-rank conjecture

Lee, T

Shraibman, A

Permalink

Publisher:: Springer Nature
Publication Type:: Journal Article
Citation:: Israel Journal of Mathematics, 2023, 256, (2), pp. 441-477
Issue Date:: 2023-09-01

Embargoed

	Filename	Description	Size
	Around the log-rank conjecture.pdf	Accepted version	345.72 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Embargoed
Open Access

This item is currently unavailable due to the publisher's embargo.

The embargo period expires on 1 Sep 2024

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Shraibman, A
dc.date.accessioned	2024-02-06T01:26:11Z
dc.date.available	2024-02-06T01:26:11Z
dc.date.issued	2023-09-01
dc.identifier.citation	Israel Journal of Mathematics, 2023, 256, (2), pp. 441-477
dc.identifier.issn	0021-2172
dc.identifier.issn	1565-8511
dc.identifier.uri	http://hdl.handle.net/10453/175342
dc.description.abstract	The log-rank conjecture states that the communication complexity of a boolean matrix A is bounded by a polynomial in the log of the rank of A. Equivalently, it says that the chromatic number of a graph is bounded quasi-polynomially in the rank of its adjacency matrix. This old conjecture is well known among computer scientists and mathematicians, but despite extensive work it is still wide open. We survey results relating to the log-rank conjecture, describing the current state of affairs and collecting related questions. Most of the results we discuss are well known, but some points of view are new. One of our hopes is to paint a path to the log-rank conjecture that is made of a series of smaller questions, which might be more feasible to tackle.
dc.language	en
dc.publisher	Springer Nature
dc.relation.ispartof	Israel Journal of Mathematics
dc.relation.isbasedon	10.1007/s11856-023-2517-5
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.rights	This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s11856-023-2517-5
dc.subject	0101 Pure Mathematics, 0102 Applied Mathematics
dc.subject.classification	General Mathematics
dc.subject.classification	4901 Applied mathematics
dc.subject.classification	4902 Mathematical physics
dc.subject.classification	4904 Pure mathematics
dc.title	Around the log-rank conjecture
dc.type	Journal Article
utslib.citation.volume	256
utslib.for	0101 Pure Mathematics
utslib.for	0102 Applied Mathematics
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	embargoed	*
utslib.copyright.embargo	2024-09-01T00:00:00+1000Z
dc.date.updated	2024-02-06T01:26:10Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	256
utslib.citation.issue	2

Abstract:

The log-rank conjecture states that the communication complexity of a boolean matrix A is bounded by a polynomial in the log of the rank of A. Equivalently, it says that the chromatic number of a graph is bounded quasi-polynomially in the rank of its adjacency matrix. This old conjecture is well known among computer scientists and mathematicians, but despite extensive work it is still wide open. We survey results relating to the log-rank conjecture, describing the current state of affairs and collecting related questions. Most of the results we discuss are well known, but some points of view are new. One of our hopes is to paint a path to the log-rank conjecture that is made of a series of smaller questions, which might be more feasible to tackle.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/175342