EUVIMEDEUVIMED entdecken
Crossref

The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds

R. Ryan Williams

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-1-FOCS24-28

DOI: 10.1137/24m1718299 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 14.10.2025. Verfasst von R. Ryan Williams. Die Arbeit nennt 81 Literaturangaben. Gefördert von: Frank Quick, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive nonuniform circuit lower bounds. We show 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 [Formula: see text]-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: [Formula: see text] There is an [Formula: see text] such that for infinitely many [Formula: see text], read-once 2-DNFs on [Formula: see text] variables cannot be simulated by nonuniform [Formula: see text]-size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class [Formula: see text] 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 [Formula: see text] disjointness matrix (well-studied in communication complexity) cannot be expressed by a linear combination of [Formula: see text] structured matrices that we call “equality matrices.” [Formula: see text] For every [Formula: see text] and every [Formula: see text], orthogonal vectors on [Formula: see text] vectors in [Formula: see text] dimensions can be solved in [Formula: see text] uniform deterministic time. This case would provide a strong refutation of the Orthogonal Vectors Conjecture, and of SETH: for example, CNF-SAT on [Formula: see text] variables and [Formula: see text] clauses could be solved in [Formula: see text] time. Moreover, this case would imply nonuniform circuit lower bounds for [Formula: see text], 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 [Formula: see text] disjointness, we derive an [Formula: see text] time and [Formula: see text] space algorithm for orthogonal vectors on [Formula: see text] vectors in [Formula: see text] dimensions. We show similar results for counting pairs of orthogonal vectors.

Förderung

  • Frank Quick
  • National Science Foundation

Zitieren

APA

Williams, R. R. (2026). The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds. SIAM Journal on Computing, 55(5), FOCS24-1-FOCS24-28. https://doi.org/10.1137/24m1718299

Vancouver

Williams RR. The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds. SIAM Journal on Computing. 2026;55(5):FOCS24-1-FOCS24-28. doi:10.1137/24m1718299

BibTeX
@article{Williams2026,
  author = {Williams, R. Ryan},
  title = {The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--1--FOCS24--28},
  doi = {10.1137/24m1718299}
}
Kostenlos starten →