A central and longstanding open problem in coding theory is the rate-versus-distance trade-off for binary error-correcting codes. In a seminal work, Delsarte introduced a family of linear programs establishing relaxations on the size of optimum codes. To date, the state-of-the-art upper bounds for binary codes come from dual feasible solutions to these LPs. Still, these bounds are exponentially far from the best-known existential constructions. Recently, hierarchies of linear programs extending and strengthening Delsarte's original LPs were introduced for linear codes, which we refer to as higher-order Delsarte LPs. These new hierarchies were shown to provably converge to the actual value of optimum codes, namely, they are complete hierarchies. Therefore, understanding them and their dual formulations becomes a valuable line of investigation. Nonetheless, their higher-order structure poses challenges. In fact, analysis of all known convex programming hierarchies strengthening Delsarte's original LPs has turned out to be exceedingly difficult and essentially nothing is known, stalling progress in the area since the 1970s. Our main result is an analysis of the higher-order Delsarte LPs via their dual formulation. Although quantitatively, our current analysis only matches the best-known upper bounds, it shows, for the first time, how to tame the complexity of analyzing a hierarchy strengthening Delsarte's original LPs. In doing so, we reach a better understanding of the structure of the hierarchy, which may serve as the foundation for further quantitative improvements. We provide two additional structural results for this hierarchy. First, we show how to \emph{explicitly} lift any feasible dual solution from level $k$ to a (suitable) larger level $\ell$ while retaining the objective value. Second, we give a novel proof of completeness using the dual formulation.

We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon–Edmonds–Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025). The main theorem demonstrates that if random linear codes satisfy the complement of an LCL property P with high probability, then one can construct explicit codes satisfying the complement of P as well, with an enlarged yet constant alphabet size. This gives the first explicit constructions for list recovery, as well as special cases (e.g., list recovery with erasures, zero-error list recovery, perfect hash matrices), with parameters matching those of random linear codes. More broadly, our constructions realize the full range of parameters associated with these properties at the same level of optimality as in the random setting, thereby offering a systematic pathway from probabilistic guarantees to explicit codes that attain them. Furthermore, our derandomization of random linear codes also admits efficient (list) decoding via recently developed expander-based decoders.

Abstract. We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost-optimal (namely, near-quadratic, [Formula: see text]) trade-off between (any desired) spectral expansion [Formula: see text] and degree [Formula: see text]. Furthermore, the algorithm is local: Every vertex in the new graph can compute its new neighbors as a subset of its original neighborhood of radius [Formula: see text]. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost-Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost-Ramanujan expanding generators. Similarly, one can obtain almost-optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost-optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [ STOC 2017 : Proceedings of the 49 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 238–251], used to obtain explicit almost-optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert–Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit operator-valued spectral amplification.

Quantum entanglement is a key enabling ingredient in diverse applications. However, the presence of unwanted adversarial entanglement also poses challenges in many applications. In this paper, we explore methods to "break" quantum entanglement. Specifically, we construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show: For every $d,\ell\ge k$, there is an efficient channel $Λ: \mathbb{C}^{d\ell} \otimes \mathbb{C}^{d\ell} \to \mathbb{C}^{dk}$ such that for every bipartite separable state $ρ_1\otimes ρ_2$, the output $Λ(ρ_1\otimesρ_2)$ is close to a k-partite separable state. Concretely, for some distribution $μ$ on states from $\mathbb{C}^d$, $$ \left\|Λ(ρ_1 \otimes ρ_2) - \int | ψ\rangle \langle ψ|^{\otimes k} dμ(ψ)\right\|_1 \le \tilde O \left(\left(\frac{k^{3}}{\ell}\right)^{1/4}\right). $$ Moreover, $Λ(| ψ\rangle \langle ψ|^{\otimes \ell}\otimes | ψ\rangle \langle ψ|^{\otimes \ell}) = | ψ\rangle \langle ψ|^{\otimes k}$. Without the bipartite unentanglement assumption, the above bound is conjectured to be impossible. Leveraging our disentanglers, we show that unentangled quantum proofs of almost general real amplitudes capture NEXP, greatly relaxing the nonnegative amplitudes assumption in the recent work of QMA^+(2)=NEXP. Specifically, our findings show that to capture NEXP, it suffices to have unentangled proofs of the form $| ψ\rangle = \sqrt{a} | ψ_+ \rangle + \sqrt{1-a} | ψ_- \rangle$ where $| ψ_+ \rangle$ has non-negative amplitudes, $| ψ_- \rangle$ only has negative amplitudes and $| a-(1-a) | \ge 1/poly(n)$ with $a \in [0,1]$. Additionally, we present a protocol achieving an almost largest possible gap before obtaining QMA^R(k)=NEXP$, namely, a 1/poly(n) additive improvement to the gap results in this equality.

Good codes over an alphabet of constant size q can approach but not surpass distance 1-1/q. This makes the use of q-ary codes a necessity in some applications, and much work has been devoted to the case of constant alphabet q. In the large distance regime, namely, distance 1-1/q-ε for small ε > 0, the Gilbert-Varshamov (GV) bound asserts that rate Ω_q(ε²) is achievable whereas the q-ary MRRW bound gives a rate upper bound of O_q(ε²log(1/ε)). In this sense, the GV bound is almost optimal in this regime. Prior to this work there was no known explicit and efficiently decodable q-ary codes near the GV bound, in this large distance regime, for any constant q ≥ 3. We design an Õ_{ε,q}(N) time decoder for explicit (expander based) families of linear codes C_{N,q,ε} ⊆ F_q^N of distance (1-1/q)(1-ε) and rate Ω_q(ε^{2+o(1)}), for any desired ε > 0 and any constant prime q, namely, almost optimal in this regime. These codes are ε-balanced,i.e., for every non-zero codeword, the frequency of each symbol lies in the interval [1/q - ε, 1/q + ε]. A key ingredient of the q-ary decoder is a new near-linear time approximation algorithm for linear equations (k-LIN) over ℤ_q on expanding hypergraphs, in particular, those naturally arising in the decoding of these codes. We also investigate k-CSPs on expanding hypergraphs in more generality. We show that special trade-offs available for k-LIN over ℤ_q hold for linear equations over a finite group. To handle general finite groups, we design a new matrix version of weak regularity for expanding hypergraphs. We also obtain a near-linear time approximation algorithm for general expanding k-CSPs over q-ary alphabet. This later algorithm runs in time Õ_{k,q}(m + n), where m is the number of constraints and n is the number of variables. This improves the previous best running time of O(n^{Θ_{k,q}(1)}) by a Sum-of-Squares based algorithm of [AJT, 2019] (in the expanding regular case). We obtain our results by generalizing the framework of [JST, 2021] based on weak regularity decomposition for expanding hypergraphs. This framework was originally designed for binary k-XOR with the goal of providing near-linear time decoder for explicit binary codes, near the GV bound, from the breakthrough work of Ta-Shma [STOC, 2017]. The explicit families of codes over prime F_q are based on suitable instatiations of the Jalan-Moshkovitz (Abelian) generalization of Ta-Shma’s distance amplification procedure.

We develop new list decoding algorithms for Tanner codes and distance-amplified codes based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the minimum distance of these codes can be used as certificates discoverable by relaxations in the Sum-of-Squares (SoS) semi-definite programming hierarchy. Combining these certificates with certain entropic proxies to ensure that the solutions to the relaxations cover the entire list, then leads to algorithms for list decoding several families of codes up to the Johnson bound. We prove the following results:- We show that the LDPC Tanner codes of Zémor [IEEE Trans. Inf. Theory 2001] with alphabet size q, block-length n and distance $\delta$, based on an expander graph with degree d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound.- We show that the codes obtained via the expander-based distance amplification procedure of Alon, Edmonds and Luby [FOCS 1995] can be list-decoded close to the Johnson bound using the SoS hierarchy, by reducing the list decoding problem to unique decoding of the base code. In particular, starting from any base code unique-decodable up to distance $\delta$, one can obtain near-MDS codes with rate R and distance $1-R-\varepsilon$, list-decodable up to the Johnson bound in time $n^{O_{\varepsilon, \delta}(1)}$.- We show that the locally testable codes of Dinur et al. [STOC 2022] with alphabet size q, block-length n and distance $\delta$ based on a square Cayley complex with generator sets of size d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound.

Determining the maximum size $A_2(n,d)$ of a binary code of blocklength $n$ and distance $d$ remains an elusive open question even when restricted to the important class of linear codes. Recently, two linear programming hierarchies extending Delsarte's LP were independently proposed to upper bound $A_2^{\text{Lin}}(n,d)$ (the analogue of $A_2(n,d)$ for linear codes). One of these hierarchies, by the authors, was shown to be approximately complete in the sense that the hierarchy converges to $A_2^{\text{Lin}}(n,d)$ as the level grows beyond $n^2$. Despite some structural similarities, not even approximate completeness was known for the other hierarchy by Loyfer and Linial. In this work, we prove that both hierarchies recover the exact value of $A_2^{\text{Lin}}(n,d)$ at level $n$. We also prove that at this level the polytope of Loyfer and Linial is integral.Even though these hierarchies seem less powerful than general hierarchies such as Sum-of-Squares, we show that they have enough structure to yield exact completeness via pseudoprobabilities.

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.

We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d\leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree d. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert-Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit (high-dimensional”) spectral amplification.

A longstanding open problem in coding theory is to determine the best (asymptotic) rate $R_2(δ)$ of binary codes with minimum constant (relative) distance $δ$. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte's linear programs. To date these results remain the best known lower and upper bounds on $R_2(δ)$ with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength. In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size $A^{\text{Lin}}_2(n,d)$ of an optimum linear binary code (in fact, over any finite field) of a given blocklength $n$ and distance $d$. This hierarchy has several notable features: (i) It is a natural generalization of the Delsarte LPs used in the first MRRW bound. (ii) It is a hierarchy of linear programs rather than semi-definite programs potentially making it more amenable to theoretical analysis. (iii) It is complete in the sense that the optimum code size can be retrieved from level $O(n^2)$. (iv) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte's LP polytopes to approximate the true size of linear codes. We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higher-order" version taking into account interactions of $\ell$ words. Our method also generalizes to translation schemes under mild assumptions.

For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.

The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є2). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є2+α), where α → 0 as є → 0. Moreover, the codes in Ta-Shma’s construction are є-balanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2.

The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Max- k-CSPs and Tensor PCA. On the flip side, a SoS lower bound provides evidence of hardness, which is particularly relevant to average-case problems for which NP-hardness may not be available. In this paper, we consider the following average case problem, which we call the Planted Affine Planes (PAP) problem: Given m random vectors d1, ..., dmin Rn, can we prove that there is no vector v ∈ IRnsuch that for all u ∈ [m], 〈v, du〉2= 1? In other words, can we prove that m random vectors are not all contained in two parallel hyperplanes at equal distance from the origin? We prove that for m ≤ n3/2-ε, with high probability, degree- nΩ(ε)SoS fails to refute the existence of such a vector v. When the vectors d1, ..., dmare chosen from the multivariate normal distribution, the PAP problem is equivalent to the problem of proving that a random n-dimensional subspace of Rmdoes not contain a boolean vector. As shown by Mohanty-Raghavendra-Xu [STOC 2020], a lower bound for this problem implies a lower bound for the problem of certifying energy upper bounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound implies a degree- nΩ(ε)SoS lower bound for the certification version of the Sherrington-Kirkpatrick problem.

The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance 1/2-ε and rate Ω(ε2) (where an upper bound of O(ε2log(1/ε)) is known). Ta-Shma [STOC 2017] gave an explicit construction of ε-balanced binary codes, where any two distinct codewords are at a distance between 1/2-ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε2+β), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for ε-balanced codes with block length N and rate Ω(ε2+β) in this family: -For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time NOε,β(1). -For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε))O(1)·NOβ(1). -For any , there are explicit ε-balanced codes with rate Ω(ε2+β) which can be list decoded up to error 1/2-ε'in time NOε,ε',β(1), where ε',β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in ε. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction.

We consider families of codes obtained by “lifting” a base code through operations such as k-XOR applied to “local views” of codewords of , according to a suitable k-uniform hypergraph. The k-XOR operation yields the direct sum encoding used in works of [Ta-Shma, STOC 2017] and [Dinur and Kaufman, FOCS 2017]. We give a general framework for list decoding such lifted codes, as long as the base code admits a unique decoding algorithm, and the hypergraph used for lifting satisfies certain expansion properties. We show that these properties are indeed satisfied by the collection of length k walks on a sufficiently strong expanding graph, and by hypergraphs corresponding to high-dimensional expanders. Instantiating our framework, we obtain list decoding algorithms for direct sum liftings corresponding to the above hypergraph families. Using known connections between direct sum and direct product, we also recover (and strengthen) the recent results of Dinur et al. [SODA 2019] on list decoding for direct product liftings. Our framework relies on relaxations given by the Sum-of-Squares (SOS) SDP hierarchy for solving various constraint satisfaction problems (CSPs). We view the problem of recovering the closest codeword to a given (possibly corrupted) word, as finding the optimal solution to an instance of a CSP. Constraints in the instance correspond to edges of the lifting hypergraph, and the solutions are restricted to lie in the base code . We show that recent algorithms for (approximately) solving CSPs on certain expanding hypergraphs by some of the authors also yield a decoding algorithm for such lifted codes. We extend the framework to list decoding, by requiring the SOS solution to minimize a convex proxy for negative entropy. We show that this ensures a covering property for the SOS solution, and the “condition and round” approach used in several SOS algorithms can then be used to recover the required list of codewords.

We consider the problem of approximately solving constraint satisfaction problems with arity k > 2 (kCSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of k-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of highdimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter γ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet [q] is a high-dimensional expander with parameter γ, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error ε using qO(k)· (k/ε)O(1)levels of the sum-of-squares SDP hierarchy, provided γ ≤ εO(1)· (1/(kq))O(k). Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank r for a threshold τ = (ε/k)O(1)· (1/q)O(k), then it is possible to approximately solve the instance up to additive error ε, using r · qO(k)· (k/ε)O(1)levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small γ) have threshold rank 1 according to our definition.