Given a constraint satisfaction problem (CSP) predicate P ⊆ D^r, the non-redundancy (NRD) of P is the maximum-sized instance on n variables such that for every clause of the instance, there is an assignment which satisfies all clauses but that one. The study of NRD for various CSPs is an active area of research which combines ideas from extremal combinatorics, logic, lattice theory, and other techniques. Complete classifications are known in the cases r = 2 and (|D| = 2, r = 3). In this paper, we give a near-complete classification of the case (|D| = 2, r = 4). Of the 400 distinct non-trivial Boolean predicates of arity 4, we implement an algorithmic procedure which perfectly classifies 397 of them. Of the remaining three, we solve two by reducing to extremal combinatorics problems - leaving the last one as an open question. Along the way, we identify the first Boolean predicate whose non-redundancy asymptotics are non-polynomial.

Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error model bridges between fully random errors and fully adversarial errors by allowing some symbols of a message to be corrupted by an adversary while others are replaced with uniformly random symbols. As our main quest, we seek to understand optimal efficient unique decoding algorithms in the semi-adversarial model. For interleaved Reed--Solomon (IRS), folded Reed--Solomon (FRS) and univariate multiplicity codes, we design decoding algorithms running in near-linear time for most mixtures of random and adversarial errors. Our analysis matches the information-theoretic optimum for semi-adversarial errors. Our algorithm for interleaved Reed--Solomon codes is an improved implementation of the decoding algorithm by Bleichenbacher--Kiayias--Yung (BKY) for fully random errors. We use a novel monomial-tracking technique to analyze its performance in this new semi-adversarial errors. Inspired by the BKY algorithm, we use novel interpolations to extend our approach to the settings of folded Reed--Solomon and multiplicity codes, resulting in fast algorithms for unique decoding against semi-adversarial errors. Our new decoders for FRS and multiplicity codes replace the sophisticated root-finding step in traditional algorithms, such as the Guruswami--Wang algorithm, with a straightforward polynomial long division. Analysis of these algorithms requires more robust monomial-tracking arguments than IRS codes.

The chain length of a set family 𝒮 ⊆ 2^[m] is the largest ascending sequence of sets in containment order in the union-closure of S. In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger’s [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC dimension characterizes the additive sparsifiability of a set system, chain length governs the multiplicative sparsifiability. As a corollary, we obtain improved bounds for weighted CSP sparsification.

The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou [SODA'13, TALG'16] is whether MAX BISECTION can be approximated as well as MAX CUT, i.e., to within \(\alpha_{\mathrm{GW}} \approx 0.8785672\ldots\), which is the approximation ratio achieved by the celebrated Goemans-Williamson algorithm for MAX CUT, which is best possible assuming the Unique Games Conjecture (UGC). They conjectured that the answer is yes.

In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023), and obtain the following results:

In coding theory, the problem of list recovery asks one to find all codewords c of a given code C which such that at least 1−ρ fraction of the symbols of c lie in some predetermined set of ℓ symbols for each coordinate of the code. A key question is bounding the maximum possible list size L of such codewords for the given code C.

In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent work Levi, Mosheiff, and Shagrithaya (FOCS 2025) gave a novel unified framework for calculating the threshold rates of local properties for random linear and random Reed–Solomon codes.

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and k designated terminals. The goal is to partition the vertices of the graph into k parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for k≥3. The currently best known approximation algorithm for the problem for arbitrary k, obtained by Sharma and Vondrák [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of k ≥ 4 we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For k=3 an optimal approximation algorithm is known.)

Abstract. Assuming the unique games conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the max cut problem is [Formula: see text], obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The current best approximation algorithm for max di-cut, i.e., the max cut problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question of whether max di-cut can be approximated as well as max cut. We obtain a slightly improved algorithm for max di-cut and a new UGC-hardness for it, showing that [Formula: see text], where [Formula: see text] is the best approximation ratio that can be obtained in polynomial time for max di-cut under UGC. Our new upper bound shows that max di-cut cannot be approximated as well as max cut, which separates max di-cut from max cut and resolves a question raised by Feige and Goemans. A natural generalization of max di-cut is the max [Formula: see text]-and problem in which each constraint is of the form [Formula: see text], where [Formula: see text] and [Formula: see text] are literals, i.e., variables or their negations (in max di-cut each constraint is of the form [Formula: see text] where [Formula: see text] and [Formula: see text] are variables). Austrin separated max [Formula: see text]-and from max cut by showing that [Formula: see text] and conjectured that max [Formula: see text]-and and max di-cut have the same approximation ratio. Our new lower bound on max di-cut refutes this conjecture, completing the separation of the three problems max [Formula: see text]-and, max di-cut, and max cut. We also obtain a new lower bound for max [Formula: see text]-and, showing that [Formula: see text]. Our upper bound on max di-cut is achieved via a simple, analytical proof. The new lower bounds on max di-cut and max [Formula: see text]-and, i.e., the new approximation algorithms, use experimentally discovered distributions of rounding functions which are then verified via computer-assisted proofs. Code for the project is available at https://github.com/jbrakensiek/max-dicut .

In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over anm×ngrid topology with one parity check per row and column of the grid along withh≥ 1 global parity checks. Previous works have largely focused on the setting in whichm = n, where explicit constructions require field size which is exponential inn. Motivated by practical applications, we consider the regime in whichm, hare constants andnis growing. In this setting, we provide a number of new explicit constructions whose field size is polynomial inn. We further complement these results with new field size lower bounds.

The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to anypolynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that the GM-MDS theorem also holds foralgebraic codes(and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [2], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam ([1]) showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang ([2]) and Alrabiah-Guruswami-Li ([3]) have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory ofrelaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we calllowerandupperrelaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah- Guruswami-Li to show that both these relaxations can be constructed by randomly puncturing suitable algebraic-geometric codes overconstant sizefields. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi ([4]). We obtain the following corollaries from our main result: • Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radiusL/L+1 (1 −R− ϵ) with list sizeLover fields of size exp(O(L/ϵ)). In particular, they achieve list-decoding capacity with list sizeO(1/ϵ) and field size exp(O(1/ϵ2)). Prior to this work, AG codes were not even known to achieve list-decoding capacity. • By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column overconstant-sizedfields, whereas (non-relaxed) MR tensor codes require exponential field size.

Austrin showed that the approximation ratio β ≈ 0.94016567 obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture that states that the worst performance of the algorithm is obtained on so called simple configurations. We prove Austrin's conjecture, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture. Our proof uses a combination of analytic and computational tools.

The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [Brakensiek, Dhar, Gopi, Zhang; 2024], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang and Alrabiah-Guruswami-Li have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory of relaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we call lower and upper relaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah-Guruswami-Li to show that both these relaxations can be constructed over constant size fields by randomly puncturing suitable algebraic-geometric codes. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi. We obtain the following corollaries from our main result: Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radius L/L+1(1−R−є) with list size L over fields of size exp(O(L/є)). In particular, they achieve list-decoding capacity with list size O(1/є) and field size exp(O(1/є2)). Prior to this work, AG codes were not even known to achieve list-decoding capacity. By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column over constant-sized fields, whereas (non-relaxed) MR tensor codes require exponential field size.

Abstract. Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the [Formula: see text] threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form [Formula: see text] with [Formula: see text] and [Formula: see text], where [Formula: see text] is any edge set such that no vertex has more than an [Formula: see text]-fraction of its edges in [Formula: see text]. We show that one can construct [Formula: see text] with [Formula: see text] that is close to [Formula: see text]. For arbitrary [Formula: see text], [Formula: see text] satisfies [Formula: see text]. Additionally, when [Formula: see text] is a mild expander, we provide a 3-coloring for [Formula: see text] in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on [Formula: see text], we show that it is NP -hard to 3-color [Formula: see text].

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek et al., (2023). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by$\rm {MDS}(\ell)$where$\ell $denotes the order of generality,$\rm {MDS}(2)$codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an${[}n,k{]}$-$\rm {MDS}(\ell)$codes is$\Omega _{\ell } (n^{\ell -1})$, whereas the best known (non-explicit) upper bound is$O_{\ell } (n^{k(\ell -1)})$which is exponential in the dimension. In this work, we nearly close this exponential gap between upper and lower bounds. We show that an${[}n,k{]}$-$\rm {MDS}(3)$codes requires a field of size$\Omega _{k}(n^{k-1})$, which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question by Shangguan and Tamo, (2020). We also give explicit constructions of${[}n,k{]}$-$\rm {MDS}(\ell)$code over fields of size$n^{(\ell k)^{O(\ell k)}}$. The smallest non-trivial case where we still do not have optimal constructions is${[}n,3{]}$-$\rm {MDS}(3)$. In this case, the known lower bound on the field size is$\Omega (n^{2})$and the best known upper bounds are$O(n^{5})$for a non-explicit construction and$O(n^{32})$for an explicit construction. In this paper, we give an explicit construction over fields of size$O(n^{3})$which comes very close to being optimal.

Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is $\alpha_{\text {CUT}} \simeq 0.87856$, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. Currently, the best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UG-Chardness result for it, showing that $0.87446 \leq \alpha_{\text {DI-CUT}} \leq 0.87461$, where $\alpha_{\text {DI-CUT}}$ is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, i.e., shows that MAX DI-CUT cannot be approximated as well as MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form $z_{1} \wedge {z_{2}}$, where $z_{1}$ and ${z_{2}}$ are literals, i.e., variables or their negations. (In MAX DI-CUT each constraint is of the form $\bar{x}_{1} \wedge {x_{2}}$, where $x_{1}$ and ${x_{2}}$ are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that $\alpha_{2 \mathrm{AND}} \leq 0.87435$ and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND showing that $0.87414 \leq \alpha_{2 \text {AND}} \leq 0.87435$. Our upper bound on MAXDI-CUT is achieved via a simple analytical proof. The new lower bounds on MAX DI-CUT and MAX 2-AND, i.e., the new approximation algorithms, use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs.11Code for the project: https://github.com/jbrakensiek/max-dicut

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by MDS(ℓ) where ℓ denotes the order of generality, MDS(2) codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an (n, k)-MDS(ℓ) codes is Ωℓ(nℓ−1), whereas the best known (non-explicit) upper bound is Oℓ(nk(ℓ−1)) which is exponential in the dimension.In this work, we nearly close this exponential gap between upper and lower bounds. We show that an (n, k)-MDS(3) codes requires a field of size Ωk(nk−1), which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question from Shangguan and Tamo (STOC 2020).We also give explicit constructions of (n, k)-MDS(ℓ) code over fields of size ${n^{{{(\ell k)}^{O(\ell k)}}}}$. The smallest non-trivial case where we still do not have optimal constructions is (n, 3)-MDS(3). In this case, the known lower bound on the field size is Ω(n2) and the best known upper bounds are O(n5) for a non-explicit construction and O(n32) for an explicit construction. In this paper, we give an explicit construction over fields of size O(n3) which comes very close to being optimal.

In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be checked by a simple local consistency algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact satisfiability of a bounded width CSP can be checked by combinatorial algorithms, the robust algorithm is based on rounding a canonical Semi Definite Programming(SDP) relaxation.

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli $M$ for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod $M$. The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod $M$, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by Nägele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite $M$.

An$(m,n,a,b)$-tensor code consists of$m\times n$matrices whose columns satisfy ‘$a$’ parity checks and rows satisfy ‘$b$’ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when$a=1$, i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes ($\mathrm {MDS}(\ell)$codes) which is an interesting generalization of the well-known MDS codes, where$\ell $captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with$a=1$is MR if the row code is an$\mathrm {MDS}(m)$code. We then show that$\mathrm {MDS}(m)$codes satisfy some weak duality. Using this characterization and duality, we prove that$(m,n,a=1,b)$-MR tensor codes require fields of size$q=\Omega _{m,b}(n^{\min \{b,m\}-1})$. Our lower bound also extends to the setting of$a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when$a=1$).

Abstract. MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size [Formula: see text] for some [Formula: see text]. We refer to this problem as MAX NAE-[Formula: see text]-SAT. For [Formula: see text], it is a slight extension of the celebrated MAX CUT problem. For [Formula: see text], it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For [Formula: see text], it is known that an approximation ratio of [Formula: see text], obtained by choosing a random assignment, is optimal, assuming [Formula: see text]. For every [Formula: see text], an approximation ratio of at least [Formula: see text] can be obtained for MAX NAE-[Formula: see text]-SAT. There was some hope, therefore, that there is also a [Formula: see text]-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no [Formula: see text]-approximation algorithm for MAX NAE-SAT, assuming the Unique Games Conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-[Formula: see text]-SAT (i.e., MAX NAE-SAT where all clauses have size 3 or 5), the best approximation ratio that can be achieved, assuming UGC, is at most [Formula: see text]. Using calculus of variations, we extend the analysis of O’Donnell and Wu for MAX CUT to MAX NAE-[Formula: see text]-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-[Formula: see text]-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is about 0.9089. This gives a full understanding of MAX NAE-[Formula: see text]-SAT for every [Formula: see text]. Interestingly, the rounding function used by this optimal algorithm is the solution of an integral equation. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-[Formula: see text]-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698. We further conjecture that these are essentially the best approximation ratios that can be achieved for these problems, assuming the UGC. Somewhat surprisingly, the rounding functions used by these approximation algorithms are nonmonotone step functions that assume only the values [Formula: see text].

A classic result due to Schaefer [ Proceedings of STOC 78, ACM, 1978, pp. 216--226] classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in ${P}$ or ${NP}$-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, \Psi_Q)$ of CSPs with the same set of variables such that for every $(P, Q) \in \Gamma$, $P(x_{i_1}, \hdots, x_{i_k})$ is a clause of $\Psi_P$ if and only if $Q(x_{i_1}, \hdots, x_{i_k})$ is a clause of $\Psi_Q$. The promise problem ${PCSP}(\Gamma)$ is to distinguish, given $(\Psi_P, \Psi_Q)$, between the cases $\Psi_P$ is satisfiable and $\Psi_Q$ is unsatisfiable. Many problems such as approximate graph and hypergraph coloring as well as the $(2+\epsilon)$-SAT problem due to Austrin, Guruswami, and H\aastad [ SIAM J. Comput., 46 (2017), pp. 1554--1573] can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean PCSPs, determining for which $\Gamma$ the associated PCSP is polynomial-time tractable or ${NP}$-hard. As our main result, we show that ${PCSP}(\Gamma)$ exhibits a dichotomy (it is either polynomial-time tractable or ${NP}$-hard) when the relations in $\Gamma$ are symmetric and allow for negations of variables. In particular, we show that every such polynomial-time tractable $\Gamma$ can be solved via either Gaussian elimination over $\mathbb F_2$ or a linear programming relaxation. We achieve our dichotomy theorem by extending the (weak) polymorphism framework of Austrin, Guruswami, and H\aastad which itself is a generalization of the algebraic approach used by polymorphisms to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case.

The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture. This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call V Label Cover . Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications: • There is an absolute constant c 0 such that for k ≥ 3, given a satisfiable instance of Boolean k -CSP, it is hard to find an assignment satisfying more than c 0 k 2 /2 k fraction of the constraints. • Given a k -uniform hypergraph, k ≥ 2, for all ε > 0, it is hard to tell if it is q -strongly colorable or has no independent set with an ε fraction of vertices, where q =⌈ k +√ k -1/2⌉. • Given a k -uniform hypergraph, k ≥ 3, for all ε > 0, it is hard to tell if it is ( k -1)-rainbow colorable or has no independent set with an ε fraction of vertices.

We prove that computing a Nash equilibrium of a two-player ( n×n) game with payoffs in [-1, 1] is PPAD-hard (under randomized reductions) even in the smoothed analysis setting, smoothing with noise of constant magnitude. This gives a strong negative answer to conjectures of Spielman and Teng [ST06] and Cheng, Deng, and Teng [CDT09]. In contrast to prior work proving PPAD-hardness after smoothing by noise of magnitude 1/poly(n) [CDT09], our smoothed complexity result is not proved via hardness of approximation for Nash equilibria. This is by necessity, since Nash equilibria can be approximated to constant error in quasi-polynomial time [LMM03]. Our results therefore separate smoothed complexity and hardness of approximation for Nash equilibria in two-player games. The key ingredient in our reduction is the use of a random zero-sum game as a gadget to produce two-player games which remain hard even after smoothing. Our analysis crucially shows that all Nash equilibria of random zero-sum games are far from pure (with high probability), and that this remains true even after smoothing.

The coded trace reconstruction problem asks to construct a code C ⊂ {0,1}nsuch that any x ∈ C is recoverable from independent outputs (“traces”) of x from a binary deletion channel (BDC). We present binary codes of rate 1-ε that are efficiently recoverable from exp(Oq(log1/3([1/(ε)]))) (a constant independent of n) traces of a BDCq for any constant deletion probability q ∈ (0,1). We also show that, for rate 1 -ε binary codes, ~Ω(log5/2(1/ε)) traces are required. The results follow from a pair of black-box reductions that show that average-case trace reconstruction is essentially equivalent to coded trace reconstruction. We also show that there exist codes of rate 1 -ε over an Oε(1)-sized alphabet that are recoverable from O(log(1/ε)) traces, and that this is tight.

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: “strict” and “weak,” and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem—which has recently benefited from multiple breakthroughs [BKO19, WZ19] due to a systematic study of promise CSPs under the lens of “polymorphisms,” operations that map tuples in the strict form of each constraint to a tuple in its weak form. In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, that is the coordinates are permutation invariant. This generalizes previous work of the authors [BG19]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic theorem and shed further light on how symmetries of polymorphisms enable algorithms.

We show that the edit distance between two strings of length n can be computed via a randomized algorithm within a factor of f(є) in n 1+є time as long as the edit distance is at least n 1−δ for some δ(є) > 0.

In the field of constraint satisfaction problems (CSPs), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: “strict” and “weak,” and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem-which has recently seen exciting progress [Bulín, Krokhin, and Oprs̆al, Proceedings of the Symposium on Theory of Computing, 2019, pp. 602--613 and Wrochna and Živný, Proceedings of the Symposium on Discrete Algorithms, 2020, pp. 1426--1435] benefiting from a systematic algebraic approach to promise CSPs based on “polymorphisms,” operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form. In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [Brakensiek and Guruswami, Proceedings of the Symposium on Discrete Algorithms, 2019, pp. 436--455]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of associated operations on the solution space called (weak) polymorphisms. However, compared to CSPs whose polymorphisms are well-structured algebraic objects called clones, polymorphisms in the promise world are much less constrained — essentially any infinite family of functions obeying mild conditions can arise as polymorphisms. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms. In previous work, we classified all tractable cases of Boolean promise CSPs when the constraint predicates are symmetric. The algorithms were governed by three kinds of polymorphism families: (i) parity functions, (ii) majority functions, or (iii) a non-symmetric (albeit block-symmetric) family we called alternating threshold. In this work, we provide a vast generalization of these algorithmic results. Specifically, we show that promise CSPs that admit a family of “regional-periodic” polymorphisms are solvable in polynomial time, assuming that determining which region a point is in can be computed in polynomial time. Such polymorphisms are quite general and are obtained by gluing together several functions that are periodic in the Hamming weights in different blocks of the input. For example, we can have functions that equal parity for relative Hamming weights up to 1/2, and Majority (so identically 1) for weights above 1/2. Our algorithm is based on a novel combination of linear programming and solving linear systems over rings. We also abstract a framework based on reducing a promise CSP to a CSP over an infinite domain, solving it there (via the said combination of LPs and ring equations), and then rounding the solution to an assignment for the promise CSP instance. The rounding step is intimately tied to the family of polymorphisms, and clarifies the connection between polymorphisms and algorithms in this context. As a key ingredient, we introduce the technique of finding a solution to a linear program with integer coefficients that lies in a different ring (such as ℤ) to bypass ad-hoc adjustments for lying on a rounding boundary.

Under the Strong Exponential Time Hypothesis, an integer linear program with n Boolean-valued variables and m equations cannot be solved in cn time for any constant c < 2. If the domain of the variables is relaxed to [0,1], the associated linear program can of course be solved in polynomial time. In this work, we give a natural algorithmic bridging between these extremes of 0-1 and linear programming. Specifically, for any subset (finite union of intervals) E ⊂ [0,1] containing {0,1}, we give a random-walk based algorithm with runtime OE((2−measure(E))npoly(n,m)) that finds a solution in En to any n-variable linear program with m constraints that is feasible over {0,1}n. Note that as E expands from {0,1} to [0,1], the runtime improves smoothly from 2n to polynomial.

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of the modulus M. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the ETH). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod M. The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod M, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study.

A classic result of Schaefer [STOC, 1978] classifies all constraint satisfaction problems (CSPs) over the Boolean domain to be either in P or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. Many problems such as approximate graph and hypergraph coloring, the (2 + ∊)-SAT problem due to Austrin, Guruswami, and Håstad [SIAM Journal on Computing, 2017], and the digraph homomorphism problem can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean PCSPs, determining which PCSPs are polynomial-time tractable or NP-hard. As our main result, we show that PCSPs exhibits a dichotomy (it is either polynomial-time tractable or NP-hard) when the clauses are symmetric and allow for negations of variables. In particular, we show that every such polynomial-time tractable instance can be solved via either Gaussian elimination over F2 or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH which itself is a generalization of the algebraic approach used by polymorphisms to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case.

We consider the problem of constructing binary codes to recover from k-bit deletions with efficient encoding/decoding, for a fixed k. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with ≈ 2n/n codewords of length n, i.e., at most log n bits of redundancy. However, even for the case of two deletions, there was no known explicit construction with redundancy less than nΩ(1). For any fixed k, we construct a binary code with cklog n redundancy that can be decoded from k deletions in Ok(n log4n) time. The coefficient ckcan be taken to be O(k2log k), which is only quadratically worse than the optimal, non-constructive bound of O(k). We also indicate how to modify this code to allow for a combination of up to k insertions and deletions. We also note that among linear codes capable of correcting k deletions, the (k + 1)-fold repetition code is essentially the best possible.

The tensor power of the clique on $t$ vertices (denoted by $K_t^n$) is the graph on vertex set $\{1, ..., t\}^n$ such that two vertices $x, y \in \{1, ..., t\}^n$ are connected if and only if $x_i \neq y_i$ for all $i \in \{1, ..., n\}$. Let the density of a subset $S$ of $K_t^n$ to be $μ(S) := \frac{|S|}{t^n}$, and let the vertex boundary of a set $S$ to be vertices which are incident to some vertex of $S$, perhaps including points of $S$. We investigate two similar problems on such graphs. First, we study the vertex isoperimetry problem. Given a density $ν\in [0, 1]$ what is the smallest possible density of the vertex boundary of a subset of $K_t^n$ of density $ν$? Let $Φ_t(ν)$ be the infimum of these minimum densities as $n \to \infty$. We find a recursive relation allows one to compute $Φ_t(ν)$ in time polynomial to the number of desired bits of precision. Second, we study given an independent set $I \subseteq K_t^n$ of density $μ(I) = \frac{1}{t}(1-ε)$, how close it is to a maximum-sized independent set $J$ of density $\frac{1}{t}$. We show that this deviation (measured by $μ(I \setminus J)$) is at most $4ε^{\frac{\log t}{\log t - \log(t-1)}}$ as long as $ε< 1 - \frac{3}{t} + \frac{2}{t^2}$. This substantially improves on results of Alon, Dinur, Friedgut, and Sudakov (2004) and Ghandehari and Hatami (2008) which had an $O(ε)$ upper bound. We also show the exponent $\frac{\log t}{\log t - \log(t-1)}$ is optimal assuming $n$ tending to infinity and $ε$ tending to $0$. The methods have similarity to recent work by Ellis, Keller, and Lifshitz (2016) in the context of Kneser graphs and other settings. The author hopes that these results have potential applications in hardness of approximation, particularly in approximate graph coloring and independent set problems.

In this paper we provide a new geometric characterization of the Hirschfeld-Gebelein-Rényi maximal correlation of a pair of random $(X,Y)$, as well as of the chordal slope of the nontrivial boundary of the hypercontractivity ribbon of $(X,Y)$ at infinity. The new characterizations lead to simple proofs for some of the known facts about these quantities. We also provide a counterexample to a data processing inequality claimed by Erkip and Cover, and find the correct tight constant for this kind of inequality.

Finding a proper coloring of a t-colorable graph G with t colors is a classic NP-hard problem when t >= 3. In this work, we investigate the approximate coloring problem in which the objective is to find a proper c-coloring of G where c >= t. We show that for all t >= 3, it is NP-hard to find a c-coloring when c <= 2t-2. In the regime where t is small, this improves, via a unified approach, the previously best known hardness result of c <= max{2t- 5, t + 2*floor(t/3) - 1} (Garey and Johnson 1976; Khanna, Linial, Safra, 1993; Guruswami, Khanna, 2000). For example, we show that 6-coloring a 4-colorable graph is NP-hard, improving on the NP-hardness of 5-coloring a 4-colorable graph. We also generalize this to related problems on the strong coloring of hypergraphs. A k-uniform hypergraph H is t-strong colorable (where t >= k) if there is a t-coloring of the vertices such that no two vertices in each hyperedge of H have the same color. We show that if t = ceiling(3k/2), then it is NP-hard to find a 2-coloring of the vertices of H such that no hyperedge is monochromatic. We conjecture that a similar hardness holds for t=k+1. We establish the NP-hardness of these problems by reducing from the hardness of the Label Cover problem, via a "dictatorship test" gadget graph. By combinatorially classifying all possible colorings of this graph, we can infer labels to provide to the label cover problem. This approach generalizes the "weak polymorphism" framework of (Austrin, Guruswami, Hastad, 2014), though interestingly our results are "PCP-free" in that they do not require any approximation gap in the starting Label Cover instance.

We consider the problem of constructing binary codes to recover from k–bit deletions with efficient encoding/decoding, for a fixed k. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with ≈ 2n/n codewords of length n, i.e., at most log n bits of redundancy. However, even for the case of two deletions, there was no known explicit construction with redundancy less than nΩ(1). For any fixed k, we construct a binary code with ck log n redundancy that can be decoded from k deletions in Ok(n log4 n) time. The coefficient ck can be taken to be O(k2 log k), which is only quadratically worse than the optimal, non-constructive bound of O(k). We also indicate how to modify this code to allow for a combination of up to k insertions and deletions. We also note that among linear codes capable of correcting k deletions, the (k + 1)-fold repetition code is essentially the best possible.