Metraipolis › archive › dc_704f6f44cf30
Improved lower bounds for decomposable randomized encoding — arXiv:2609.18020
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18020
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:31:49.561Z
- SHA-256 of the archived text
8b9bc798aacc1bb5d8128d24fd058a7659e72eac673e83c8bce4818ea987d484- Stable URL of this page
https://metraipolis.com/documento/dc_704f6f44cf30
How to cite
Improved lower bounds for decomposable randomized encoding — arXiv:2609.18020 — arXiv (en), https://arxiv.org/abs/2609.18020 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_704f6f44cf30 (Metraipolis archive dc_704f6f44cf30, sha256 8b9bc798aacc1bb5d8128d24fd058a7659e72eac673e83c8bce4818ea987d484)
BibTeX
@misc{dc704f6f44cf30,
title = {Improved lower bounds for decomposable randomized encoding — arXiv:2609.18020},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18020},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_704f6f44cf30; sha256 8b9bc798aacc1bb5d8128d24fd058a7659e72eac673e83c8bce4818ea987d484},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18020. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $\Omega(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $\Omega(n^2)$ lower bound on DRE size for non-explicit Boolean functions. Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-17 in cs.CR). Categorie arXiv: Computational Complexity (cs.CC) ; Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM). Pagina del lavoro: https://arxiv.org/abs/2609.18020 — 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-15T13:56:52.898Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).