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 O (n) -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 >0 such that for infinitely many n, read-once 2-DNFs on n variables cannot be simulated by non-uniform 2^ n -size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class E^N P 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 2ⁿ 2ⁿ Disjointness Matrix (well-studied in communication complexity) cannot be expressed by a linear combination of 2^o (n) structured matrices that we call “equality matrices”. • For every c 1 and every >0, Orthogonal Vectors on n vectors in c n dimensions can be solved in n^1+ uniform deterministic time. This case would provide a strong refutation of the Orthogonal Vectors conjecture, and of SETH: for example, CNF-SAT on n variables and O (n) clauses could be solved in 2^n / 2+o (n) time. Moreover, this case would imply non-uniform circuit lower bounds for the class E^NP, 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 2⁶ 2⁶ Disjointness, we derive an O (n 6^d / 6) O (n 1. 35ᵈ̇) time and n poly (n, d) space algorithm for Orthogonal Vectors on n vectors in d dimensions. We show similar results for counting pairs of orthogonal vectors.