Skip to content
Preprint

XOR-Functions and Beyond in the Random Query Model

Nov 2026 · 0 citations
Computer Science

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{\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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.