Log-rank conjecture

Last updated February 15, 2023

Unsolved problem in computer science:

Prove or disprove the log-rank conjecture.

(more unsolved problems in computer science)

In theoretical computer science, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix.^[1]^[2]

Let $D(f)$ denote the deterministic communication complexity of a function, and let $\operatorname {rank} (f)$ denote the rank of its input matrix $M_{f}$ (over the reals). Since every protocol using up to $c$ bits partitions $M_{f}$ into at most $2^{c}$ monochromatic rectangles, and each of these has rank at most 1,

D(f)\geq \log _{2}\operatorname {rank} (f).

The log-rank conjecture states that $D(f)$ is also upper-bounded by a polynomial in the log-rank: for some constant $C$ ,

D(f)=O((\log \operatorname {rank} (f))^{C}).

The best known upper bound, due to Lovett,^[3] states that

D(f)=O\left({\sqrt {\operatorname {rank} (f)}}\log \operatorname {rank} (f)\right).

The best known lower bound, due to Göös, Pitassi and Watson,^[4] states that $C\geq 2$ . In other words, there exists a sequence of functions $f_{n}$ , whose log-rank goes to infinity, such that

D(f_{n})={\tilde {\Omega }}((\log \operatorname {rank} (f_{n}))^{2}).

In 2019, an approximate version of the conjecture has been disproved.^[5]

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties each receive a $-bit string and . The goal is for Alice to compute the value of a certain function,, that depends on both and, with the least amount of communication between them.$

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n² time but not n time.

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.

In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.

In computational complexity theory, P, also known as PTIME or DTIME(n^O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector space or free modules are generally considered.

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.

In theoretical computer science, a pseudorandom generator for low-degree polynomials is an efficient procedure that maps a short truly random seed to a longer pseudorandom string in such a way that low-degree polynomials cannot distinguish the output distribution of the generator from the truly random distribution. That is, evaluating any low-degree polynomial at a point determined by the pseudorandom string is statistically close to evaluating the same polynomial at a point that is chosen uniformly at random.

In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex $and vertex ?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer. A property satisfying this conjecture is called evasive.$

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity.

References

↑ Lovász, László; Saks, Michael (1988), Möbius Functions and Communication Complexity, Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, pp. 81–90
↑ Lovett, Shachar (February 2014), "Recent advances on the log-rank conjecture in communication complexity", Bulletin of the EATCS, 112, arXiv: 1403.8106
↑ Lovett, Shachar (March 2016), "Communication is Bounded by Root of Rank", Journal of the ACM, 63 (1): 1:1–1:9, arXiv: 1306.1877 , doi:10.1145/2724704, S2CID 47394799
↑ Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018), "Deterministic Communication vs. Partition Number", SIAM Journal on Computing, 47 (6): 2435–2450, doi:10.1137/16M1059369
↑ Chattopadhyay, Arkadev; Mande, Nikhil; Sherif, Suhail (2019), The Log-Approximate-Rank Conjecture is False, Annual ACM Symposium on the Theory of Computing, Phoenix, Arizona, USA

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Lovász, László; Saks, Michael (1988), Möbius Functions and Communication Complexity, Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, pp. 81–90

[2] Lovett, Shachar (February 2014), "Recent advances on the log-rank conjecture in communication complexity", Bulletin of the EATCS, 112, arXiv: 1403.8106

[3] Lovett, Shachar (March 2016), "Communication is Bounded by Root of Rank", Journal of the ACM, 63 (1): 1:1–1:9, arXiv: 1306.1877 , doi:10.1145/2724704, S2CID 47394799

[4] Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018), "Deterministic Communication vs. Partition Number", SIAM Journal on Computing, 47 (6): 2435–2450, doi:10.1137/16M1059369

[5] Chattopadhyay, Arkadev; Mande, Nikhil; Sherif, Suhail (2019), The Log-Approximate-Rank Conjecture is False, Annual ACM Symposium on the Theory of Computing, Phoenix, Arizona, USA

[1]

[2]

[3]

[4]

[5]