The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential approach to refuting the Orthogonal Vectors Conjecture in the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> -dimensional case, which would be sufficient for refuting the Strong Exponential Time Hypothesis (SETH). For example, we show that at least one of the following holds: • There is an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon&gt;0$</tex> such that for infinitely many <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>, read-once 2-DNFs on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> variables cannot be simulated by non-uniform <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{\varepsilon n}$</tex> -size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$E^{N P}$</tex> does not have polynomial-size depth-two exact threshold circuits, so such a lower bound would be a significant advance in low-depth circuit complexity. In fact, a stronger lower bound holds in this case: the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^n \times 2^n$</tex> Disjointness Matrix (well-studied in communication complexity) cannot be expressed by a linear combination of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{o(n)}$</tex> structured matrices that we call “equality matrices”. • For every <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$c \geq 1$</tex> and every <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon&gt;0$</tex>, Orthogonal Vectors on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> vectors in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$c \log n$</tex> dimensions can be solved in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{1+\varepsilon}$</tex> uniform deterministic time. This case would provide a strong refutation of the Orthogonal Vectors conjecture, and of SETH: for example, CNF-SAT on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> variables and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n)$</tex> clauses could be solved in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{n / 2+o(n)}$</tex> time. Moreover, this case would imply non-uniform circuit lower bounds for the class <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$E^{NP}$</tex>, against Valiant series-parallel circuits. Inspired by this connection, we give evidence from SAT/SMT solvers that the first item (in particular, the Disjointness lower bound) may be false in its full generality. In particular, we present a systematic approach to solving Orthogonal Vectors via constant-sized decompositions of the Disjointness Matrix, which already yields interesting new algorithms. For example, using a linear combination of 6 equality matrices that express <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^6 \times 2^6$</tex> Disjointness, we derive an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}\left(n \cdot 6^{d / 6}\right) \leq \tilde{O}\left(n \cdot 1. \dot{35^d}\right)$</tex> time and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \cdot \operatorname{poly}(\log n, d)$</tex> space algorithm for Orthogonal Vectors on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> vectors in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> dimensions. We show similar results for counting pairs of orthogonal vectors.