Metraipolis › archive › dc_1d035abb63d8
Quadratic-Time Barriers from Self-Referential SAT — arXiv:2611.07308
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07308
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:54:20.125Z
- SHA-256 of the archived text
20f53744cc031c22ac447a8f288865e1385b5fb71bc6285622a2bd3f1e7e2d4c- Stable URL of this page
https://metraipolis.com/documento/dc_1d035abb63d8
How to cite
Quadratic-Time Barriers from Self-Referential SAT — arXiv:2611.07308 — arXiv (en), https://arxiv.org/abs/2611.07308 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1d035abb63d8 (Metraipolis archive dc_1d035abb63d8, sha256 20f53744cc031c22ac447a8f288865e1385b5fb71bc6285622a2bd3f1e7e2d4c)
BibTeX
@misc{dc1d035abb63d8,
title = {Quadratic-Time Barriers from Self-Referential SAT — arXiv:2611.07308},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07308},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1d035abb63d8; sha256 20f53744cc031c22ac447a8f288865e1385b5fb71bc6285622a2bd3f1e7e2d4c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07308. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in $O(n^{2-\eta})$ time for any fixed $\eta>0$, where $n$ is the longer sequence length. The same exclusion holds for one-dimensional dynamic time warping on $\{0,1,2,4,8\}$ with absolute-difference cost and for five-symbol dynamic time warping with the discrete metric. We derive Orthogonal Vectors hardness in polylogarithmic dimension by splitting the variables of the logarithmic-width source formula into two halves. Existing sequence reductions have polynomial overhead in the dimension. Their output lengths and construction times allow a fixed saving in the target exponent to yield a fixed proportional saving in the source exponent.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.07308 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.628Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).