[SOLVED] CS Skip to main content

Skip to main content

We gratefully acknowledge support from
the Simons Foundation and member institutions.
arXiv.org > cs > arXiv:1403.8106
Help | Advanced Search
All fields
Title
Author
Abstract
Comments
Journal reference
ACM classification
MSC classification
Report number
arXiv identifier
DOI
ORCID
arXiv author ID
Help pages
Full text

Search
Computer Science > Computational Complexity
[Submitted on 31 Mar 2014]
Recent advances on the log-rank conjecture in communication complexity
Shachar Lovett
The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this conjecture. Recently, there has been renewed interest in this conjecture and its relations to other fundamental problems in complexity theory. This survey describes some of the recent progress, and hints at potential directions for future research.
Comments:
arXiv admin note: text overlap with arXiv:1306.1877
Subjects:
Computational Complexity (cs.CC); Combinatorics (math.CO)
MSC classes:
68Q10
ACMclasses:
F.1.2; F.2.2
Journalreference:
Lovett, Shachar. Recent advances on the log-rank conjecture in communication complexity. Bulletin of EATCS 1.112 (2014)
Cite as:
arXiv:1403.8106 [cs.CC]

(or arXiv:1403.8106v1 [cs.CC] for this version)
Submission history
From: Shachar Lovett [view email]
[v1] Mon, 31 Mar 2014 17:55:55 UTC (15 KB)
Download:
PDF
PostScript
Other formats
(license)
Current browse context:
cs.CC
<prev | next>
new | recent | 1403
Change to browse by:
cs
math
math.CO
References & Citations
NASA ADS
Google Scholar
Semantic Scholar

1 blog link (what is this?)
DBLP CS Bibliography
listing | bibtex
Shachar Lovett
Export Bibtex Citation
Bookmark

Bibliographic Tools
Bibliographic and Citation Tools

Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Code
Related Papers
About arXivLabs
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

AboutHelp
contact arXivClick here to contact arXivContactsubscribe to arXiv mailingsClick here to subscribeSubscribe
CopyrightPrivacy Policy
Web Accessibility AssistancearXiv Operational Status Get status notifications via email or slack