A Note on the LogRank Conjecture in Communication Complexity

Vince Grolmusz ()
Additional contact information
Vince Grolmusz: Department of Computer Science, Eötvös Loránd University, H-1117 Budapest, Hungary

Mathematics, 2023, vol. 11, issue 22, 1-10

Abstract: The LogRank conjecture of Lovász and Saks (1988) is the most famous open problem in communication complexity theory. The statement is as follows: suppose that two players intend to compute a Boolean function f ( x , y ) when x is known for the first and y for the second player, and they may send and receive messages encoded with bits, then they can compute f ( x , y ) with exchanging ( log rank ( M f ) ) c bits, where M f is a Boolean matrix, determined by function f . The problem is widely open and very popular, and it has resisted numerous attacks in the last 35 years. The best upper bound is still exponential in the bound of the conjecture. Unfortunately, we cannot prove the conjecture, but we present a communication protocol with ( log rank ( M f ) ) c bits, which computes a (somewhat) related quantity to f ( x , y ) . The relation is characterized by the representation of low-degree, multi-linear polynomials modulo composite numbers. Our result may help to settle this long-open conjecture.

Keywords: logrank conjecture; communication complexity; composite modulus; hyperdense coding (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/22/4651/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/22/4651/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:22:p:4651-:d:1280697

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().