Metraipolis › archive › dc_c5b76da25797
The Complexity of Unpredictability — arXiv:2611.05956
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05956
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:32:02.230Z
- SHA-256 of the archived text
969e4c032a79c713a3ed5b500eeb34bdb821c742bc9ef2e3ca45ebd7090e8948- Stable URL of this page
https://metraipolis.com/documento/dc_c5b76da25797
How to cite
The Complexity of Unpredictability — arXiv:2611.05956 — arXiv (en), https://arxiv.org/abs/2611.05956 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c5b76da25797 (Metraipolis archive dc_c5b76da25797, sha256 969e4c032a79c713a3ed5b500eeb34bdb821c742bc9ef2e3ca45ebd7090e8948)
BibTeX
@misc{dcc5b76da25797,
title = {The Complexity of Unpredictability — arXiv:2611.05956},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05956},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c5b76da25797; sha256 969e4c032a79c713a3ed5b500eeb34bdb821c742bc9ef2e3ca45ebd7090e8948},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05956. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $\epsilon>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+\epsilon$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.05956 — 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-05T18:21:34.063Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).