The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive nonuniform circuit lower bounds. In this talk, I will show in depth how the nonexistence of nontrivial circuit-analysis algorithms can also imply nonuniform 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(logn)-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 ε greater than 0 such that for infinitely many n, read-once 2-DNFs on n variables cannot be simulated by nonuniform 2εn-size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class ENP 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 2n×2n disjointness matrix (well-studied in communication complexity) cannot be expressed by a linear combination of 2o(n)

structured matrices that we call “equality matrices.”

For every c greater than or equal to 1 and every ε greater than 0, orthogonal vectors on n vectors in clogn dimensions can be solved in n1+ε 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 2n/2+o(n) time. Moreover, this case would imply nonuniform circuit lower bounds for ENP, against Valiant series-parallel circuits.

Inspired by this connection, we have found 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 26×26

disjointness, we derive an Õ (n⋅6d/6) less than or equal to Õ (n⋅1.35d) time and n⋅poly(logn,d) space algorithm for orthogonal vectors on n vectors and d dimensions. We show similar results for counting pairs of orthogonal vectors.