We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^*$, and then (2) sampling constraints from a particular "planting distribution" designed so that $x^*$ will satisfy every constraint. Given an $n$ variable instance of a $k$-ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$, and succeeds in outputting a satisfying assignment if $m \geq O(n) \cdot (n/\ell)^{\frac{k}{2} - 1} \log n$. This generalizes the $\mathrm{poly}(n)$-time algorithm of [FPV15], the case of $\ell = O(1)$, to larger runtimes, and matches the constraint number vs.\ runtime trade-off established for refuting random CSPs by [RRS17]. Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a $\mathrm{poly}(n)$-time algorithm to solve semirandom CSPs with $m \geq \tilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^*$ exactly. Instead, we forego certificates of uniqueness and recover $x^*$ in two steps: we first use a degree-$O(\ell)$ Sum-of-Squares SDP to find some $\hat{x}$ that is $o(1)$-close to $x^*$, and then we use a second rounding procedure to recover $x^*$ from $\hat{x}$.

A code $\mathcal{C}:\{0,1\}^{k} \rightarrow\{0,1\}^{n}$ is a q-query locally decodable code (q-LDC) if one can recover any chosen bit $b_{i}$ of the message $b \in\{0,1\}^{k}$ with good confidence by querying a corrupted string $\tilde{x}$ of the codeword $x=\mathcal{C}(b)$ in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length $n=2^{k}$, and this code is in fact essentially optimal [1], [2]. For $q \geq 3$, there is a large gap in our understanding: the best constructions achieve $n=\exp \left(k^{o(1)}\right)$, while prior to the recent work of [3], the best lower bounds were $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for q even and $n \geq \tilde{\Omega}\left(k^{\frac{q+1}{q-1}}\right)$ for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of $n \geq \tilde{\Omega}\left(k^{3}\right)$ for q = 3, thus achieving the “ $k^{\frac{q}{q-2}}$ bound” for an odd value of q. However, their proof does not extend to any odd $q \geq 5$. In this paper, we prove a q-LDC lower bound of $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for any odd q. Our key technical idea is the use of an imbalanced bipartite Kikuchi graph, which gives a simpler method to analyze spectral refutations of odd arity XOR without using the standard “Cauchy-Schwarz trick” ― a trick that typically produces random matrices with nontrivially correlated entries and makes the analysis for odd arity XOR significantly more complicated than even arity XOR.

We give improved lower bounds for binary 3-query locally correctable codes (3-LCCs)$C: \{\ 0,1 \}^k \rightarrow \{\ 0,1 \}^n$. Specifically, we prove: 1) If C is a linear design 3-LCC, then$n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching, and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor$\sqrt{8}$in the exponent of 2, as the best construction of binary 3-LCCs (obtained by taking Reed--Muller codes on F_4 and applying a natural projection map) is a design 3-LCC with$n \leq 2^{\sqrt{8 k}}$. Up to a factor of 8, this resolves the Hamada conjecture on the maximum F_2-codimension of a 4-design. 2) If C is a smooth, non-linear, adaptive 3-LCC with perfect completeness, then,$n \geq 2^{\Omega(k^{1/5})}$. 3) If C is a smooth, non-linear, adaptive 3-LCC with completeness 1 - \eps, then n \geq \Omega(k^{\frac${1}{2\eps}}). In particular, when$\eps$is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best$n \geq \Omega(k^3)$lower bound of Alrabiah-Guruswami-Kothari-Manohar by a polynomial factor. Our design LCC lower bound is obtained via a fine-grained analysis of the Kikuchi matrix method applied to a variant of the matrix used in the work of Kothari and Manohar (2023). Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear 3-LCCs to a system of “chain XOR equations” — polynomial equations with a similar structure to the long chain derivations that arise in the lower bounds for linear 3-LCCs of Kothari and Manohar.

We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L ∶ Fk → Fn with distance δ must be at least n ≥ 2Ω((δ2 k/(|F|−1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n ≥ Ω(k3), which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on binary Reed–Muller codes, which achieve n ≤ 2O(k1/2). Because there is a 3-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first strong separation between q-query LCCs and LDCs for any constant ‍q ≥ 3. Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances. Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations — a structured variant of low-width resolution for XOR formulas from proof complexity.

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst case and average case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^{*}$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution “shifted by $x^{*}$” so that $x^{*}$ satisfies each constraint. For an n variable semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}\left(n^{k / 2}\right)$ constraints. This matches, up to ${\mathrm {polylog}} (n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [23], as well as algorithms that refute random and semirandom CSPs [1], [4]. Our result shows that despite having worst case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst case, where analogous results require $O\left(n^{k}\right)$ constraints [7], [26]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices — reminiscent of the classical spectral sparsification — which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.

In this work, we revisit the problem of estimating the mean and covariance of an unknown $d$-dimensional Gaussian distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. The work of Diakonikolas et al. (2016) gave a polynomial time algorithm for this task with optimal $\tilde{O}(\varepsilon)$ error using $n = \textrm{poly}(d, 1/\varepsilon)$ samples. On the other hand, Kothari and Steurer (2017) introduced a general framework for robust moment estimation via a canonical sum-of-squares relaxation that succeeds for the more general class of \emph{certifiably subgaussian} and \emph{certifiably hypercontractive} (Bakshi and Kothari, 2020) distributions. When specialized to Gaussians, this algorithm obtains the same $\tilde{O}(\varepsilon)$ error guarantee as Diakonikolas et al. (2016) but incurs a super-polynomial sample complexity ($n = d^{O(\log 1/\varepsilon)}$) and running time ($n^{O(\log(1/\varepsilon))}$). This cost appears inherent to their analysis as it relies only on sum-of-squares certificates of upper bounds on directional moments while the analysis in Diakonikolas et al. (2016) relies on \emph{lower bounds} on directional moments inferred from algebraic relationships between moments of Gaussian distributions. We give a new, simple analysis of the \emph{same} canonical sum-of-squares relaxation used in Kothari and Steurer (2017) and Bakshi and Kothari (2020) and show that for Gaussian distributions, their algorithm achieves the same error, sample complexity and running time guarantees as of the specialized algorithm in Diakonikolas et al. (2016). Our key innovation is a new argument that allows using moment lower bounds without having sum-of-squares certificates for them. We believe that our proof technique will likely be useful in designing new robust estimation algorithms.

Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices. Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes. On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.

We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(ℓ) time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2 - 1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs.

We prove that with high probability over the choice of a random graph G from the Erdős-Rényi distribution G(n, 1/2), a natural n^{O(ε² log n)}-time, degree O(ε² log n) sum-of-squares semidefinite program cannot refute the existence of a valid k-coloring of G for k = n^{1/2 + ε}. Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovász theta function) cannot be appreciably improved by a natural o(log n)-degree sum-of-squares strengthening, and this is tight up to a n^{o(1)} slack in k. To the best of our knowledge, this is the first lower bound for coloring G(n, 1/2) for even a single round strengthening of the basic SDP in any SDP hierarchy. Our proof relies on a new variant of instance-preserving non-pointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [Boaz Barak et al., 2016; S. B. {Hopkins} et al., 2017; Dmitriy Kunisky and Afonso S. Bandeira, 2019; Mrinalkanti Ghosh et al., 2020; Mohanty et al., 2020]. Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions. We prove that low-degree testing in the non-signaling setting is possible, assuming that the locality of the non-signaling function exceeds a threshold. We additionally show that if the locality is below the threshold then the test fails spectacularly, in that there exists a non-signaling function which passes the test with probability 1 and yet is maximally far from being low-degree. Along the way, we present general results about the local testability of linear codes in the non-signaling setting. These include formulating natural definitions that capture the condition that a non-signaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by formulating a logical inference system for linear constraints on non-signaling functions that is complete and sound.

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that "local views" follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests. In this paper we study tests that only consider restrictions along axis-parallel hyperplanes, which have been studied by Polishchuk and Spielman (1994) and Ben-Sasson and Sudan (2006). While such tests are necessarily "weaker", they work for a more general class of codes, namely tensor product codes. Moreover, axis-parallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; Ben-Sasson, Sudan 2008; Meir 2010). We present two results on axis-parallel tests. (1) Bivariate low-degree testing with low-agreement. We prove an analogue of the Bivariate Low-Degree Testing Theorem of Polishchuk and Spielman in the low-agreement regime, albeit with much larger field size. Namely, for the 2-wise tensor product of the Reed-Solomon code, we prove that for sufficiently large fields, the 2-query variant of the axis-parallel line test (row-vs-column test) works for arbitrarily small agreement. Prior analyses of axis-parallel tests assumed high agreement, and no results for such tests in the low-agreement regime were known. Our proof technique deviates significantly from that of Polishchuk and Spielman, which relies on algebraic methods such as Bezout's Theorem, and instead leverages a fundamental result in extremal graph theory by Kovari, Sos, and Turan. To our knowledge, this is the first time this result is used in the context of low-degree testing. (2) Improved robustness for tensor product codes. Robustness is a strengthening of local testability that underlies many applications. We prove that the axis-parallel hyperplane test for the m-wise tensor product of a linear code with block length n and distance d is Omega(d^m/n^m)-robust. This improves on a theorem of Viderman (2012) by a factor of 1/poly(m). While the improvement is not large, we believe that our proof is a notable simplification compared to prior work.