Metraipolis › archive › dc_0e4ea171ba71
XOR-Functions and Beyond in the Random Query Model — arXiv:2611.04353
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04353
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:07:27.902Z
- SHA-256 of the archived text
088d3a2f6f35e1a62961e369cbb45213baec603f43f1c54037129ba34d94469e- Stable URL of this page
https://metraipolis.com/documento/dc_0e4ea171ba71
How to cite
XOR-Functions and Beyond in the Random Query Model — arXiv:2611.04353 — arXiv (en), https://arxiv.org/abs/2611.04353 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0e4ea171ba71 (Metraipolis archive dc_0e4ea171ba71, sha256 088d3a2f6f35e1a62961e369cbb45213baec603f43f1c54037129ba34d94469e)
BibTeX
@misc{dc0e4ea171ba71,
title = {XOR-Functions and Beyond in the Random Query Model — arXiv:2611.04353},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04353},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0e4ea171ba71; sha256 088d3a2f6f35e1a62961e369cbb45213baec603f43f1c54037129ba34d94469e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04353. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model. On input $x$, a branching program receives independent samples $(i,x(i))$, where $i$ is uniform in $[n]$. We want to evaluate $f(x)$ while minimizing the width $2^S$ and the length $T$ of the branching program. There is a simple upper bound of $T = \tilde{O}(n)$, $S = O(n)$: coupon-collector shows that $\tilde{O}(n)$ samples suffice, and they can be stored in $O(n)$ space. Raz and Zhan (ITCS 2020) introduced this model and studied the zero-error setting. In the bounded-error setting, Dinur (SODA 2024) proved $TS = \tilde{\Omega}(n \cdot inf[f])$, where $inf[f]$ is the total influence of $f$. For many functions with low influence such as Equality and Tribes, this lower bound can leave a substantial gap from the best known upper bounds. Our main result is a stronger lower bound of $T(S+\log T) = \Omega(n \cdot sens[g])$ for any XOR-function $g(x,y)= f(x \oplus y)$, where $sens[g]$ is the sensitivity of $g$. Through simple corollaries, we get tight nearly-quadratic time--space lower bounds for Tribes and Equality, despite their low influence. Our proof introduces a new notion of information complexity tailored to the random query model along with a corresponding direct-sum argument which may be of independent interest. Dinur also proved a tight bound of $TS = \Omega(n^2)$ for Majority, whose influence is only $\Theta(\sqrt{n})$, and asked whether an alternative characterization of Boolean functions could give a unified proof of tight results for a broader class of functions, including Majority. We answer this open question by proving $TS = \tilde{\Omega}(n \cdot dgn[f])$, where $dgn[f]$ is the degeneracy of the sensitivity graph of $f$ (for Majority, this is $\Theta(n)$). We also prove that this bound is tight for all symmetric functions up to logarithmic factors.
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.04353 — 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-04T18:40:52.436Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).