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}$.

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices \(\mathcal{A}=\{A_1,A_2,\ldots,A_r\}\subseteq \mathbb{R}^{n\times n}\), given any subset \(T\subseteq [r]\), our goal is to find sparse weights \(\mu_i\in\mathbb{R}_{\ge 0}\) such that \((1-\varepsilon)\sum_{i\in T} A_i \;\preceq\; \sum_{i\in T} \mu_i A_i \;\preceq\; (1+\varepsilon)\sum_{i\in T} A_i\). This generalizes spectral sparsification of graphs which corresponds to \(\mathcal{A}\) being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., \(\mathbb{F}_2^n\)). Prior work shows any sum of PSD matrices can be sparsified down to \(O(n)\) elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection \(\mathcal{A}\)) theory of PSD matrix sparsification based on a new parameter \(N^*(\mathcal{A})\) which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most \(O(\varepsilon^{-2} N^*(\mathcal{A}) (\log n) (\log r))\) matrices and is constructible in randomized polynomial time. We also show that we need \(N^*(\mathcal{A})\) elements to sparsify for any \(\varepsilon \lt 0.99\). As the main application of our framework, we prove that any Cayley graph can be sparsified to \(O(\varepsilon^{-2}\log^4 N)\) generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is \(\mathbb{F}_2^n\).

We prove that for every odd q ⩾ 3, any q-query binary, possibly non-linear locally decodable code (q-LDC) E : {±1}k→ {±1}nmust satisfy k ⩽ Õ(n1−2/q). For even q, this bound was established in a sequence of works [KT00], [GKST06], [KW04]. For q = 3, the above bound was achieved in a recent work [AGKM23] using an argument that crucially exploits known exponential lower bounds for 2-LDCs. Their strategy hits an inherent bottleneck for q ⩾ 5.Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called t-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size t (i.e., its co-degree) be equal to the same but arbitrary value dtup to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to dt. This condition significantly generalizes related proposals in prior works [GKM22], [HKM23], [AGKM23], [HKM+24] that demand absolute upper bounds on all co-degrees.We give an argument based on spectral bounds on Kikuchi Matrices that lower bounds the blocklength of any LDC whose local decoding sets satisfy t-approximate strong regularity for any t ⩽ q. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary q-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.