| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow></semantics></math></inline-formula> when <i>x</i> is known for the first and <i>y</i> for the second player, and they may send and receive messages encoded with bits, then they can compute <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow></semantics></math></inline-formula> with exchanging <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow><mo>(</mo><mi>log</mi><mo> </mo><mi>rank</mi><mrow><mo>(</mo><msub><mi>M</mi><mi>f</mi></msub><mo>)</mo></mrow><mo>)</mo></mrow><mi>c</mi></msup></semantics></math></inline-formula> bits, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>M</mi><mi>f</mi></msub></semantics></math></inline-formula> is a Boolean matrix, determined by function <i>f</i>. 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow><mo>(</mo><mi>log</mi><mo> </mo><mi>rank</mi><mrow><mo>(</mo><msub><mi>M</mi><mi>f</mi></msub><mo>)</mo></mrow><mo>)</mo></mrow><mi>c</mi></msup></semantics></math></inline-formula> bits, which computes a (somewhat) related quantity to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow></semantics></math></inline-formula>. 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.
|
|---|