ECCC-Report TR24-142https://eccc.weizmann.ac.il/report/2024/142Comments and Revisions published for TR24-142en-usTue, 17 Sep 2024 20:39:08 +0300
Paper TR24-142
| The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds |
Ryan Williams
https://eccc.weizmann.ac.il/report/2024/142A 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(\log 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:
$\bullet$ There is an $\varepsilon > 0$ such that for infinitely many $n$, read-once 2-DNFs on $n$ variables cannot be simulated by non-uniform $2^{\varepsilon n}$-size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class $E^{NP}$ 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^n \times 2^n$ 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''.
$\bullet$ For every $c \geq 1$ and every $\varepsilon > 0$, Orthogonal Vectors on $n$ vectors in $c \log n$ dimensions can be solved in $n^{1+\varepsilon}$ 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^6 \times 2^6$ Disjointness, we derive an $\tilde{O}(n \cdot 6^{d/6}) \leq \tilde{O}(n \cdot 1.35^d)$ time and $n \cdot poly(\log n, d)$ space algorithm for Orthogonal Vectors on $n$ vectors in $d$ dimensions. We show similar results for counting pairs of orthogonal vectors.
Tue, 17 Sep 2024 20:39:08 +0300https://eccc.weizmann.ac.il/report/2024/142