Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model

The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length T and width 2 S attempts to compute a function f : 0, 1 n → 0, 1. However, instead of receiving direct access to the input bits (x 1 , . . . , x n ), the input is given in pairs of the form (i j , x ij ) ∈ 1, . . . , n × 0, 1 for j = 1, 2, . . . , T, where the indices i 1 , . . . , i T are chosen at random from a pre-fixed distribution.

Raz and Zhan proved that any branching program in the random-query model with the independent distribution (where i j j=1,...,T are uniform and independent) that computes a function f with sensitivity k satisfies T • (S + log n) ≥ Ω(n • k). This gives a quadratic time-space lower bound for many natural functions which have sensitivity Ω(n), such as XOR and Majority. The bound was proved in the zero-error regime, where for each input, the branching program is required to output a value with high probability, and given that a value is output, it must be correct with probability 1.

Furthermore, Raz and Zhan conjectured that (up to logarithmic factors in n) a quadratic time-space lower bound still holds for the XOR function in the more conventional bounded-error regime, where for each input, the output must be correct with high probability.

In this paper, we prove this conjecture. More generally, let f : 0, 1 n → 0, 1 have average sensitivity (or total influence) I[f ]. We prove that any branching program in the random-query model with the independent distribution that computes f in the bounded-error regime satisfies T • S ≥ Ω(n) • I[f ] (where Ω hides logarithmic factors in n). Moreover, we prove a quadratic time-space lower bound for the Majority function, even though its total influence is Θ( √ n).

Our proof is based on a reduction from a communication complexity problem.