Metraipolis › archive › dc_fd5140c99cf0
Randomized Lifting for One-Way Number-on-Forehead Communication — arXiv:2609.32542
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.32542
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:43:19.299Z
- SHA-256 of the archived text
565b31fb6758a517aee19ca7e0061c2c1626db4ef97400f84cf5abcb34b5963e- Stable URL of this page
https://metraipolis.com/documento/dc_fd5140c99cf0
How to cite
Randomized Lifting for One-Way Number-on-Forehead Communication — arXiv:2609.32542 — arXiv (en), https://arxiv.org/abs/2609.32542 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd5140c99cf0 (Metraipolis archive dc_fd5140c99cf0, sha256 565b31fb6758a517aee19ca7e0061c2c1626db4ef97400f84cf5abcb34b5963e)
BibTeX
@misc{dcfd5140c99cf0,
title = {Randomized Lifting for One-Way Number-on-Forehead Communication — arXiv:2609.32542},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.32542},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd5140c99cf0; sha256 565b31fb6758a517aee19ca7e0061c2c1626db4ef97400f84cf5abcb34b5963e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32542. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.32542 — 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-08T00:17:42.542Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).