Metraipolis › archive › dc_cf980cb55d13
Explicit unbalanced 1-expanders with small degree and right size — arXiv:2609.14587
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14587
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:16:29.428Z
- SHA-256 of the archived text
54c87b1ce2ed7838d668088486d66645253a0a6e48f22920f785184c4e9e6ce1- Stable URL of this page
https://metraipolis.com/documento/dc_cf980cb55d13
How to cite
Explicit unbalanced 1-expanders with small degree and right size — arXiv:2609.14587 — arXiv (en), https://arxiv.org/abs/2609.14587 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cf980cb55d13 (Metraipolis archive dc_cf980cb55d13, sha256 54c87b1ce2ed7838d668088486d66645253a0a6e48f22920f785184c4e9e6ce1)
BibTeX
@misc{dccf980cb55d13,
title = {Explicit unbalanced 1-expanders with small degree and right size — arXiv:2609.14587},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14587},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cf980cb55d13; sha256 54c87b1ce2ed7838d668088486d66645253a0a6e48f22920f785184c4e9e6ce1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14587. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An explicit graph is given with left size $N$, left degree $\widetilde O(\log^2 N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K' \le K$ has at least $K'$ neighbors. Let $\C(x)$ be the minimal length of a program that prints~$x$ (i.e., the central concept in Kolmogorov complexity). The $1$-expander is used to obtain an algorithm that on input $x$ computes in time $\poly(|x|)$ a list with $\widetilde O(|x|^3)$ programs such that at least 1 program prints $x$ and has length $\C(x) + O(1)$. This improves on the $O(|x|^{6+\eps})$ upper bound in~\cite{zim:c:shortlistshortproof} and is close to the $\Omega(|x|^2)$ lower bound from~\cite[theorem 4]{bmvz:j:shortlist}. In the companion paper ``Online matching games in bipartite expanders: applications to data structures," the $1$-expander is used to obtain dynamic dictionaries in which the query operation has non-adaptive memory access.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.14587 — 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-10-16T01:56:43.432Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).