Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan · 2025

Read Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case by Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22265.txt.

Introduction

Venkatesan Guruswami and co-authors strengthen, in a 2025 paper, lower bounds on what data structures must pay to answer queries, by simplifying a bridge to random-looking logic puzzles. A recent breakthrough tied such bounds to the refutation of pseudorandom constraint problems and to avoiding a circuit's output range. This paper routes the argument through XOR refutation instead, a cleaner channel. It also settles the odd-arity case that the earlier work left open.

The core claim says a stretching shallow circuit's output is almost surely far from well-mixed samples, and that fact can be certified efficiently. Read one way, that yields cell-probe lower bounds; read another, range avoidance algorithms. The authors frame the result as completing a derandomization of the best semi-random refutation analyses. Simpler proofs, they hope, will travel further.

Catalog record

CREATORVenkatesan Guruswami, Xin Lyu, Weiqiang Yuan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22265

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan Abstract A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of NC 0 \text{NC}^{0} circuits, and the refutation of pseudorandom CSP instances, leading to improvements to some longstanding lower bounds in the cell-probe/bit-probe models. Here, we improve these lower bounds in certain cases via a more streamlined reduction to XOR refutation, coupled with handling the odd-arity case. Our result can be viewed as a complete derandomization of the state-of-the-art semi-random k k -XOR refutation analysis (Guruswami, Kothari and Manohar, STOC 2022, Hsieh, Kothari and Mohanty, SODA 2023), which complements the derandomization of the even-arity case obtained by Korten et al. As our main technical statement, we show that for any multi-output constant-depth circuit that substantially stretches its input, its output is very likely far from strings sampled from distributions with sufficient independence, and further this can be efficiently certified. Via suitable shifts in perspectives, this gives applications to cell-probe lower bounds and range avoidance algorithms for 𝐍𝐂 0 \mathbf{NC}^{0} circuits. 1 Introduction A recent work by Korten, Pitassi, and Impagliazzo [ KPI25 ] improved some longstanding static data structure lower bounds, based on an insightful connection to range avoidance of \mathsf{NC}^{0} circuits and refutation of pseudorandom CSP instances [ KPI25 ] . In this work, we improve their cell-probe lower bounds in certain cases, using methods to refute odd-arity semi-random XOR, while streamlining some aspects of the proof, such as the reduction to k -XOR instances. Furthermore, our use of Fourier analysis for the reduction not only cleans up the bound, but also gives clear and direct improvements over [ KPI25 ] ’s lower bounds (for bit -probe data structures) and algorithms (for range avoidance) for all ranges of arities (both odd and even). We first state our main technical result, which says that for every simple circuit that stretches its input substantially, its output will almost certainly be far from a string sampled from any distribution with sufficient independence. Furthermore, this property can be certified (with high probability) via a polynomial-time algorithm. This refutation result then yields, via suitable shifts in perspective (including the recent connections made in [ KPI25 ] ), improved data structure lower bounds and range avoidance algorithms for simple circuits. We will only describe the context of these applications briefly, referring the reader to the excellent introduction of [ KPI25 ] for further discussion concerning these connections. Roadmap of Introduction. We introduce our main refutation result in Section 1.1 . Applications to data structure lower bounds and range avoidance algorithms will be delivered in Section 1.2 and Section 1.3 , respectively. Finally, Section 1.4 gives a broad overview of our proofs. 1.1 Certifying Remote Points for Simple Circuits. Given a circuit C:\{\pm 1\}^{n}\to\{\pm 1\}^{m} and a string y\in\{\pm 1\}^{m} , the statement that y\in\mathrm{Range}(C) is clearly in \mathbf{NP} . We are interested in the complexity of the negated statement “ y\notin\mathrm{Range}(C) .” Observe that this is a \mathbf{coNP} statement by definition. We ask: under which conditions can we certify that y\notin\mathrm{Range}(C) with a computation less powerful than \mathbf{coNP} ? Note that an analogous question has been asked and thoroughly investigated for CSP refutation: namely, given a SAT instance \psi , the claim that \psi is satisfiable is clearly in \mathbf{NP} and easily verifiable (given a witness), while \psi being unsatisfiable is generally harder to verify. Notation. Before formally stating our main result alluded to above, we need some pieces of notation. For two Boolean strings x,y\in\{\pm 1\}^{m} of the same length m , we use \Delta(x,y):=\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}\{x_{i}\neq y_{i}\} to denote their (relative) Hamming distance. A distribution \mathcal{D} on \{0,1\}^{m} is said to be \eta -almost k -wise independent distribution if the projection of \mathcal{D} onto any k coordinates is at most \eta -far (in infinity norm) from the uniform distribution on \{\pm 1\}^{k} in total variation distance. We now state our main result. Theorem 1 (Main) . There is a universal constant c_{\text{remote}}>0 such that the following is true. Let k,t,w,n,m\geq 1 be integer parameters satisfying k\geq t\log n and let \varepsilon\in(0,1) . Further, let \Sigma be a finite alphabet of size 2^{w} , and \mathcal{D} be a distribution over \{\pm 1\}^{m} that is \eta -almost k -wise independent where \eta\leq(2^{-tw}\cdot\varepsilon^{4}\cdot n^{-\frac{k}{\log n}})^{O(1)} . Let C:\Sigma^{n}\to\{\pm 1\}^{m} be an arbitrary multi-output circuit. Suppose each output of C(x)_{i} , 1\leq i\leq m , can be computed by a t -query (adaptive) decision tree over the input x . Then, provided that m\geq c_{\text{remote}}\cdot n\cdot\biggl(\frac{n\log n}{k}\biggr)^{t/2-1}\cdot\log(n)\cdot\varepsilon^{-4}\cdot 2^{O(tw)}\ , the following holds: \displaystyle\Pr_{\bm{b}\sim\mathcal{D}}\left[\min_{x\in\Sigma^{n}}\{\Delta(C(x,*),\bm{b})\}\geq\frac{1}{2}-\varepsilon\right]\geq 1-\frac{1}{\mathrm{poly}(n)}\ . Furthermore, there is a deterministic algorithm running in time \mathrm{poly}(m,n^{O(t)}) such that, with probability 1-\frac{1}{\mathrm{poly}(n)} over \bm{b}\sim\mathcal{D} , the algorithm certifies 1 1 1 This is to say, the algorithm always outputs either “certified” or “uncertain,” and outputs “certified” with probability 1-\frac{1}{\mathrm{poly}(n)} over the choice of \bm{b} . Whenever the algorithm outputs “certified,” the claimed bound on \Delta(C(x,*),\bm{b}) is guaranteed to hold. the bound given the input C and \bm{b} . Near-optimal constructions of almost independent distributions are well-known [ NN93 , AGHP92 ] . Specifically, the distribution \mathcal{D} required in Theorem 1 can be sampled with O(\log(n)+k+\log(1/\eta))\leq O(k+\log(1/\varepsilon)+tw+\log(n)) bits and the sampling algorithm (given random seeds) is efficient. Consequently, Theorem 1 implies that there exists an explicit ensemble of \mathrm{poly}(n,2^{k},1/\varepsilon) Boolean strings of length m , such that for any circuit C:\Sigma^{n}\to\{\pm 1\}^{m} obeying the form of Theorem 1 , a randomly drawn string from the ensemble is far away from the range of C with high probability. In Section 3 , we collect a list of pseudorandom distributions that we frequently use throughout the paper. Discussion. We compare Theorem 1 with what is known in the literature. When each output C_{i} is a simple predicate (such as XOR, OR, NAE, etc.) over at most t inputs, and \bm{b} is drawn from the uniform distribution, this is precisely the question of semi-random CSP refutation, and there has been a rather rich literature (see, e.g. [ Fei07 , AGK21 , GKM25 , HKM23 ] ). In particular, it has already been observed in [ Fei02 , COCF10 ] that refuting general t -CSPs can be reduced to strongly 2 2 2 “Strong refutation” means to certify not only that the CSP instance is unsatisfiable, but also that any assignment cannot satisfy more than \frac{1}{2}+\varepsilon fraction of constraints. refuting t -XOR instances. Motivated by the challenge of proving static data structure lower bounds with adaptive query strategies, the recent work of [ KPI25 ] initiated the quest to investigate the case of C_{i} ’s being low-depth decision trees and, more importantly, the case when \bm{b} is drawn from a pseudorandom distribution. Theorem 1 represents a new advance in this direction. In particular, when t is even, Theorem 1 provides the same quantitative bound as the main result of [ KPI25 ] . The case of odd t ’s was highlighted as an open problem in [ KPI25 , Open Problem 1] , which is affirmatively answered by Theorem 1 . We thus bring all of what is known about semi-random CSP refutation with truly random

Read the complete text