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 t
he literals re-randomized with some small probability. For an $n$-variable smoothed instance of a $k$-arity CSP, our algorithm runs in $n^{O(ell)}$ 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 $tilde{O}(n) (frac{n}{ell})^{frac{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 [RRS17]. We also make a surprising new connection between our algorithm and even covers in hypergraphs, which we use to positively resolve Feiges 2008 conjecture, an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the spectral threshold of $n^{k/2}$, extending the celebrated result for random 3-SAT of Feige, Kim and Ofek [FKO06].
Random subspaces $X$ of $mathbb{R}^n$ of dimension proportional to $n$ are, with high probability, well-spread with respect to the $ell_p$-norm (for $p in [1,2]$). Namely, every nonzero $x in X$ is robustly non-sparse in the following sense: $x$ is $
varepsilon |x|_p$-far in $ell_p$-distance from all $delta n$-sparse vectors, for positive constants $varepsilon, delta$ bounded away from $0$. This $ell_p$-spread property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and, for $p = 2$, corresponds to $X$ being a Euclidean section of the $ell_1$ unit ball. Explicit $ell_p$-spread subspaces of dimension $Omega(n)$, however, are not known except for $p=1$. The construction for $p=1$, as well as the best known constructions for $p in (1,2]$ (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of sparse matrices. We study the spread properties of the kernels of sparse random matrices. Rather surprisingly, we prove that with high probability such subspaces contain vectors $x$ that are $o(1)cdot |x|_2$-close to $o(n)$-sparse with respect to the $ell_2$-norm, and in particular are not $ell_2$-spread. On the other hand, for $p < 2$ we prove that such subspaces are $ell_p$-spread with high probability. Moreover, we show that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the $ell_p$ norm, and this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the $ell_1$ norm [BGI+08]. Instantiating this with explicit expanders, we obtain the first explicit constructions of $ell_p$-spread subspaces and $ell_p$-RIP matrices for $1 leq p < p_0$, where $1 < p_0 < 2$ is an absolute constant.
We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call emph{visible rank}. The locality constraints of a linear code are stipulated b
y a matrix $H$ of $star$s and $0$s (which we call a stencil), whose rows correspond to the local parity checks (with the $star$s indicating the support of the check). The visible rank of $H$ is the largest $r$ for which there is a $r times r$ submatrix in $H$ with a unique generalized diagonal of $star$s. The visible rank yields a field-independent combinatorial lower bound on the rank of $H$ and thus the co-dimension of the code. We prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called emph{symmetric spanoid}, which was introduced by Dvir, Gopi, Gu, and Wigderson~cite{DGGW20}. Using this connection and a construction of appropriate stencils, we answer a question posed in cite{DGGW20} and demonstrate that symmetric spanoid rank cannot improve the currently best known $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-query locally correctable codes (LCCs) of length $n$. We also study the $t$-Disjoint Repair Group Property ($t$-DRGP) of codes where each codeword symbol must belong to $t$ disjoint check equations. It is known that linear $2$-DRGP codes must have co-dimension $Omega(sqrt{n})$. We show that there are stencils corresponding to $2$-DRGP with visible rank as small as $O(log n)$. However, we show the second tensor of any $2$-DRGP stencil has visible rank $Omega(n)$, thus recovering the $Omega(sqrt{n})$ lower bound for $2$-DRGP. For $q$-LCC, however, the $k$th tensor power for $kle n^{o(1)}$ is unable to improve the $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-LCCs by a polynomial factor.
We prove that there exists an absolute constant $delta>0$ such any binary code $Csubset{0,1}^N$ tolerating $(1/2-delta)N$ adversarial deletions must satisfy $|C|le 2^{text{poly}log N}$ and thus have rate asymptotically approaching 0. This is the firs
t constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants $A$ and $delta>0$ such that any set $Csubset{0,1}^N$ of $2^{log^A N}$ binary strings must contain two strings $c$ and $c$ whose longest common subsequence has length at least $(1/2+delta)N$. As an immediate corollary, we show that $q$-ary codes tolerating a fraction $1-(1+2delta)/q$ of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be sat
isfied vs. even the weak form cannot be satisfied. Since their formal introduction by Austrin, Guruswami, and Haa stad, there has been a flurry of works on PCSPs [BBKO19,KO19,WZ20]. The key tool in studying PCSPs is the algebraic framework developed in the context of CSPs where the closure properties of the satisfying solutions known as the polymorphisms are analyzed. The polymorphisms of PCSPs are much richer than CSPs. In the Boolean case, we still do not know if dichotomy for PCSPs exists analogous to Schaefers dichotomy result for CSPs. In this paper, we study a special case of Boolean PCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate $x leq y$. In the algebraic framework, this is the special case of Boolean PCSPs when the polymorphisms are monotone functions. We prove that Boolean Ordered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1 Conjecture [BKM21] which is a perfect completeness surrogate of the Unique Games Conjecture. Assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP can be solved in polynomial time if for every $epsilon>0$, it has polymorphisms where each coordinate has Shapley value at most $epsilon$, else it is NP-hard. The algorithmic part of our dichotomy is based on a structural lemma that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. Of independent interest, we show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.
An $(n,r,h,a,q)$-Local Reconstruction Code is a linear code over $mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$ local parity checks to recover from `$a$ er
asures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience -- namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to `$a$ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$-MR LRCs with field size $q$ bounded by $left(Oleft(max{r,n/r}right)right)^{min{h,r-a}}$. This improves upon known constructions in many relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=Theta(sqrt{n})$, $r-a=Theta(sqrt{n})$ and $h$ is a fixed constant with $hle a+2$, achieving the optimal field size of $Theta_{h}(n^{h/2}).$ Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory.
We give an efficient algorithm to strongly refute emph{semi-random} instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm matches (up to polylogarithmic factors) the best-known bounds for effic
ient refutation of fully random instances. Our main technical contribution is an algorithm to strongly refute semi-random instances of the Boolean $k$-XOR problem on $n$ variables that have $widetilde{O}(n^{k/2})$ constraints. (In a semi-random $k$-XOR instance, the equations can be arbitrary and only the right-hand sides are random.) One of our key insights is to identify a simple combinatorial property of random XOR instances that makes spectral refutation work. Our approach involves taking an instance that does not satisfy this property (i.e., is emph{not} pseudorandom) and reducing it to a partitioned collection of $2$-XOR instances. We analyze these subinstances using a carefully chosen quadratic form as a proxy, which in turn is bounded via a combination of spectral methods and semidefinite programming. The analysis of our spectral bounds relies only on an off-the-shelf matrix Bernstein inequality. Even for the purely random case, this leads to a shorter proof compared to the ones in the literature that rely on problem-specific trace-moment computations.
Suppose that $mathcal{P}$ is a property that may be satisfied by a random code $C subset Sigma^n$. For example, for some $p in (0,1)$, $mathcal{P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $
pn$. We say that $R^*$ is the threshold rate for $mathcal{P}$ if a random code of rate $R^{*} + varepsilon$ is very likely to satisfy $mathcal{P}$, while a random code of rate $R^{*} - varepsilon$ is very unlikely to satisfy $mathcal{P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably symmetric. For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property $mathcal{P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib wh
o proposed a hypergraph version of this conjecture, and also studied its implied fraction
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 be
ing 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 [BKO19, WZ20] 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 [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 Schaefers 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
