Search

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 no(1) 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 H = (V,E) with V = V (K3 G) and E = E(K3 G) s E, where E E(K3 G) is any edge set such that no vertex has more than an -fraction of its edges in E. We show that one can construct H = K3 \times G with V (H) = V (H) that is close to H. For arbitrary G, H satisfies | E(H)Δ E H)| O(\epsilon | E(H)|). Additionally, when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

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: \sanstwo -\sansS \sansA \sansT, \sansH \sansO \sansR \sansN -\sansS \sansA \sansT, and \sansL \sansI \sansN -\sanstwo (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 \sansH \sansO \sansR \sansN -\sansS \sansA \sansT case is connected to the covering complexity of polynomials representing the \sansN \sansA \sansN \sansD function mod M. The \sansL \sansI \sansN -\sanstwo case is tied to the sparsity of polynomials representing the \sansO \sansR 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\"agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for \sansH \sansO \sansR \sansN -\sansS \sansA \sansT 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. [ABSTRACT FROM AUTHOR]

A classic result due to Schaefer (1978) 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 Γ consists of a pair (ΨP,ΨQ) of CSPs with the same set of variables such that for every (P,Q)∈Γ, P(xi1,...,xik) is a clause of ΨP if and only if Q(xi1,...,xik) is a clause of ΨQ. The promise problem PCSP(Γ) is to distinguish, given (ΨP,ΨQ), between the cases ΨP is satisfiable and ΨQ is unsatisfiable. Many natural problems including approximate graph and hypergraph coloring can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs. As our main result, we show that PCSP(Γ) exhibits a dichotomy (it is either polynomial time solvable or NP-hard) when the relations in Γ are symmetric and allow for negations of variables. We achieve our dichotomy theorem by extending the weak polymorphism framework of Austrin, Guruswami, and Håstad [FOCS '14] which itself is a generalization of the algebraic approach 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. Furthermore, we show that the computational complexity of any promise CSP (over arbitrary finite domains) is captured entirely by its weak polymorphisms, a feature known as Galois correspondence, as well as give necessary and sufficient conditions for the structure of this set of weak polymorphisms. Such insights call us to question the existence of a general dichotomy for Boolean PCSPs case. [ABSTRACT FROM AUTHOR]

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 Oprsal, Proceedings of the Symposium on Theory of Computing, 2019, pp. 602--613 and Wrochna and Zivny, 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. [ABSTRACT FROM AUTHOR]

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 \approx ~2^n/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^{\Omega (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 \log ^{4} n) time. The coefficient ck can be taken to be O(k^2 \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. [ABSTRACT FROM PUBLISHER]