arXiv preprint ·
XOR-Functions and Beyond in the Random Query Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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Ω(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) = Ω(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 = Ω(n^2)$ for Majority, whose influence is only $Θ(\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Ω(n \cdot dgn[f])$, where $dgn[f]$ is the degeneracy of the sensitivity graph of $f$ (for Majority, this is $Θ(n)$). We also prove that this bound is tight for all symmetric functions up to logarithmic factors.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Semidirect sums of tensors and the matrix multiplication exponent
Sublinear Metric Distortion for Matching
Incremental Open Addressing Has No Time-Space Tradeoff
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.