XOR-Functions and Beyond in the Random Query Model

We study time--space tradeoffs for computing Boolean functions f:\0,1\ⁿ → \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 2S and the length T of the branching program. There is a simple upper bound of T = Õ(n), $S = O(n)$: coupon-collector shows that Õ(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 = Ω(n · 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 · sens[g]) for any XOR-function g(x,y)= f(x ⊕ 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²) for Majority, whose influence is only Θ(√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 = Ω(n · 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.