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.

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.

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:

A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of NC0 circuits, and the refutation of pseudorandom CSP instances, leading to improvements to some longstanding lower bounds in the cell-probe/bit-probe models. Here, we improve these lower bounds in certain cases via a more streamlined reduction to XOR refutation, coupled with handling the odd-arity case. Our result can be viewed as a complete derandomization of the state-of-the-art semi-random \(k\)-XOR refutation analysis (Guruswami, Kothari and Manohar, STOC 2022, Hsieh, Kothari and Mohanty, SODA 2023), which complements the derandomization of the even-arity case obtained by Korten et al.

Reed-Solomon (RS) codes were recently shown to exhibit an intriguing proximity gap phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are δ-close to RS codewords, or most of them are δ-far from the code. Here δ is the proximity parameter which can be taken to be the Johnson radius 1−√R of the RS code (R being the code rate), matching its best known list-decodability. Proximity gaps play a crucial role in the soundness analysis of Interactive Oracle Proof (IOP) protocols used in Succinct Non-Interactive Arguments of Knowledge (SNARKs) and the resulting proof sizes.

Abstract The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $$(1-\varepsilon )$$ ( 1 - ε ) -satisfiable (where the parameter is the number of variables) for some constant $$0<\varepsilon <1$$ 0 < ε < 1 . We consider a minimization version of CSPs (Min CSP), where one may assign r values to each variable, and the goal is to ensure that every constraint is satisfied by some choice among the $$r \times r$$ r × r pairs of values assigned to its variables (call such a CSP instance r list satisfiable). We prove the following strong parameterized inapproximability for Min CSP: For every $$r \ge 1$$ r ≥ 1 , it is $${\mathsf {W[1]}}$$ W [ 1 ] -hard to tell if a 2CSP instance is satisfiable or is not even r list satisfiable. We refer to this statement as “Baby PIH," following the recently proved Baby PCP Theorem (Barto and Kozik, 2021). Our proof adapts the combinatorial arguments underlying the Baby PCP theorem, overcoming some basic obstacles that arise in the parameterized setting. Furthermore, our reduction runs in time polynomially bounded in both the number of variables and the alphabet size and thus implies the Baby PCP theorem as well.

Abstract. We consider the task of certifying that a random [Formula: see text]-dimensional subspace [Formula: see text] in [Formula: see text] is well-spread—every vector [Formula: see text] satisfies [Formula: see text]. In a seminal work, Barak et al. [ Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 307–326] showed a polynomial-time certification algorithm when [Formula: see text]. On the other hand, when [Formula: see text], the certification task is information-theoretically possible but there is evidence that it is computationally hard [C. Mao and A. S. Wein, Optimal Spectral Recovery of a Planted Vector in a Subspace, preprint, arXiv:2105.15081, 2021; H. Chen and T. d’Orsi, Proc. Mach. Learn, Res, (PMLR), 178 (2022), pp. 1–31], a phenomenon known as the information-computation gap. In this paper, we give subexponential-time certification algorithms in the [Formula: see text] regime. Our algorithm runs in time [Formula: see text] when [Formula: see text], establishing a smooth tradeoff between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension tradeoff for this task.

Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random for an adversary that does not have the secret key, but anyone with the secret key is able to efficiently decode corrupted codewords. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a polynomial number of codewords from random with better than $o(1)$ advantage. 2. We revisit the construction of [CG24] and show that it can be based on a wider range of assumptions than presented in [CG24]. To do this, we introduce a weakened version of the planted XOR assumption which we call the weak planted XOR assumption and which may be of independent interest. 3. We initiate the study of PRCs which are secure against space-bounded adversaries. We show how to construct secret-key PRCs of length $O(n)$ which are $\textit{unconditionally}$ indistinguishable from random by $\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.

We establish a density variant of the Frankl–Rödl theorem on the sphere 𝕊^{n-1}, which concerns avoiding pairs of vectors with a specific distance, or equivalently, a prescribed inner product. In particular, we establish lower bounds on the probability that a randomly chosen pair of such vectors lies entirely within a measurable subset A ⊆ 𝕊^{n-1} of sufficiently large measure. Additionally, we prove a density version of spherical avoidance problems, which generalize from pairwise avoidance to broader configurations with prescribed pairwise inner products. Our framework encompasses a class of configurations we call inductive configurations, which include simplices with any prescribed inner product -1 < r < 1. As a consequence of our density statement, we show that all inductive configurations are sphere Ramsey.

The first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).

In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message, a bitstring x, into a codeword. The receiver (Bob) decodes x correctly whenever there is at most a small constant fraction of adversarial errors in the transmitted codeword. We investigate the setting where Bob is restricted to be a low-space streaming algorithm. Specifically, Bob receives the message as a stream and must process it and write x in order to a write-only tape while using low (say polylogarithmic) space. Note that such a primitive then allows the execution of any downstream streaming computation on x. We show three basic results about this setting, which are informally as follows: [(i)] 1) There is a stream decodable code of near-quadratic length, resilient to error-fractions approaching the optimal bound of 1/4. 2) There is no stream decodable code of sub-quadratic length, even to correct any small constant fraction of errors. 3) If Bob need only compute a private linear function of the bits of x, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. Our constructions use locally decodable codes with additional functionality in the decoding, and (for the result on linear functions) repeated tensoring. Our lower bound, which rather surprisingly demonstrates a strong information-theoretic limitation originating from a computational restriction, proceeds via careful control of the message indices that may be output during successive blocks of the stream, a task complicated by the arbitrary state of the decoder during the algorithm.

Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results for all these variants using a novel approach that even bypasses the PCP theorem. Our main result is that it is NP-hard (under randomized reductions) to approximate the sparsest vector in a real subspace within any constant factor; the gap can be further amplified using tensoring. Our reduction has the property that there is a Boolean solution in the completeness case. As a corollary, this immediately recovers the state-of-the-art inapproximability factors for the shortest vector problem (SVP) on lattices. Our proof extends the range of $\mathbf{l}_{\_} \mathbf{p}$ (quasi) norms for which hardness was previously known, from ‘p at least one’ to ‘p at least zero’, answering a question raised by (Khot, JACM 2005).Previous hardness results for SVP, and the related minimum distance problem (MDP) for error-correcting codes, all use lattice/coding gadgets that have an abundance of codewords in a ball of radius smaller than the minimum distance. In contrast, our reduction only needs many codewords in a ball of radius slightly larger than the minimum distance. This enables an easy derandomization of our reduction for finite fields, giving a new elementary proof of deterministic hardness for MDP. We believe this weaker density requirement might offer a promising approach to showing deterministic hardness of SVP, a long elusive goal. The key technical ingredient underlying our result for real subspaces is a proof that in the kernel of a random Rademacher matrix, the support of any two linearly independent vectors have very little overlap.A broader motivation behind this work is the development of inapproximability techniques for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which appear to be out of reach of current PCP techniques. We hope that the approach we develop could enable progress on some of these problems.

It is a major challenge to construct good quantum codes supporting fault-tolerant (e.g. transversal) non-Clifford gates with low-weight parity-check measurements. In this paper, we construct the first known quantum codes with linear dimension and distance supporting transversal non-Clifford gates that have sublinear locality (i.e. parity-check weight). Specifically, we construct codes with transversal CCZ gates that have dimension and distance growing linearly in the block length, and have locality growing as the square root of the block length. We furthermore design an efficient decoding algorithm for these codes. The alphabet size of these codes grows as the square root of the block length, but it can be reduced to a constant (e.g. binary) while incurring a polylogarithmic loss in other parameters. We also show how to decrease the locality to the cube root of the block length, albeit with a larger alphabet size and slightly lower distance.We construct these codes as products of classical codes with appropriate algebraic structure. While our quantum codes are subsystem codes with non-commuting gauge operators, we show they nevertheless permit error correction from noisy syndrome measurements.As byproducts, we prove multiple technical results of independent interest. In particular, our efficient decoder can be viewed as a new multivariate generalization of Prony’s method for reconstructing a function from partial access to its Fourier transform. Meanwhile, our distance analysis involves new connections to the classical study of maximally recoverable codes. Our results on product codes also resolve a conjecture of Bravyi & Hastings (2014) in the large-alphabet regime, by providing a new construction of quantum codes with linear dimension and distance and small polynomial locality.

Classical locally recoverable codes, which permit highly efficient recovery from localized errors as well as global recovery from larger errors, provide some of the most useful codes for distributed data storage in practice. In this paper, we initiate the study of quantum locally recoverable codes (qLRCs). In the long term, like their classical counterparts, such qLRCs may be used for large-scale quantum data storage. Furthermore, our results have concrete implications for quantum LDPC codes, which are widely applicable to near-term quantum error-correction, as local recoverability is a weakening of the LDPC property.

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ϵ> 0 such that for any computable function f:λ.,•→λ.,•, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1-ϵ fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC'24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1-o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1-o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a "vector-structured"ETH-hard CSP whose satisfiability can be checked via an appropriate form of "parallel"PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing.

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

Abstract. 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, who proposed a hypergraph version of this conjecture and also studied its implied fractional versions. We establish the fractional version of the Aharoni–Zerbib conjecture up to lower order terms. Specifically, we give a factor [Formula: see text] approximation based on LP rounding for an algorithmic version of the hypergraph Turán problem ([Formula: see text]). The objective in [Formula: see text] is to pick the smallest collection of [Formula: see text]-sized subsets of vertices of an input [Formula: see text]-uniform hypergraph such that every hyperedge contains one of these subsets. Aharoni and Zerbib also posed whether Tuza’s conjecture and its hypergraph versions could follow from nontrivial duality gaps between vertex covers and matchings on hypergraphs that exclude certain subhypergraphs, for instance, a “tent” structure that cannot occur in the incidence of triangles and edges. We give a strong negative answer to this question by exhibiting tent-free hypergraphs, and indeed [Formula: see text]-free hypergraphs for any finite family [Formula: see text] of excluded subhypergraphs, whose vertex covers must include almost all the vertices. The algorithmic questions arising in the above study can be phrased as instances of vertex cover on simple hypergraphs, whose hyperedges can pairwise share at most one vertex. We prove that the trivial factor [Formula: see text] approximation for vertex cover is hard to improve for simple [Formula: see text]-uniform hypergraphs. However, for set cover on simple [Formula: see text]-vertex hypergraphs, the greedy algorithm achieves a factor [Formula: see text], better than the optimal [Formula: see text] factor for general hypergraphs.

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rateRcodes are not list-decodable using list-sizeLbeyond an error fractionL/L+1 (1-R) (the Singleton bound being the case ofL= 1, i.e., unique decoding). We prove that in order to approach this bound for any fixedL> 1, one needs exponential alphabets. Specifically, for everyL> 1 andR∈ (0, 1), if a rateRcode can be list-of-Ldecoded up to error fractionL/L+1 (1 -R- ε), then its alphabet must have size at least exp(ΩL,R(1/ε)). This is in sharp contrast to the situation for unique decoding where certain families of rateRalgebraic-geometry (AG) codes over an alphabet of sizeO(1/ε2) are unique-decodable up to error fraction (1 -R- ε)/2. Our bounds hold even for subconstant ε ≥ 1/n, implying that any code exactly achieving theL-th generalized Singleton bound requires alphabet size 2ΩL,R(n). Previously this was only known only forL= 2 under the additional assumptions that the code is both linear and MDS. Our lower bound is tight up to constant factors in the exponent—with high probability random codes (or, as shown recently, even random linear codes) over exp(OL(1/ε))-sized alphabets, can be list-of-Ldecoded up to error fractionL/L+1 (1-R- ε).

In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if$\approx \frac {1}{3}$of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding$\frac {1}{4}$. In the corresponding setting of erasures rather than bit flips, feedback improves the error resilience from$\frac {1}{2}-\epsilon $to$1-\epsilon $for any$\epsilon \gt 0$. The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired$\epsilon \gt 0$, we construct a coding scheme that tolerates a$ 1/3-\epsilon $fraction of bit flips (respectively a$1-\epsilon $fraction of erasures) relying only on$O_{\epsilon } (\log k)$bits of feedback from Bob sent in a fixed$O_{\epsilon } (1)$number of rounds. We complement this with a matching lower bound showing that$\Omega (\log k)$bits of feedback are necessary to recover from an error fraction exceeding$1/4$(respectively$1/2$for erasures), and for schemes resilient to a$1/3-\epsilon $fraction of bit flips (respectively a$1-\epsilon $fraction of erasures), the number of rounds must grow as$\epsilon \to 0$.

We present an explicit construction of a sequence of rate$1/2$Wozencraft ensemble codes (over any fixed prime field$\mathbb {F}_{q}$) that achieve minimum distance$\Omega (\sqrt {k})$where k is the message length. The coefficients of the Wozencraft ensemble codes are constructed using Sidon Sets and the cyclic structure of$\mathbb {F}_{q^{k}}$where$k+1$is prime with q a primitive root modulo$k+1$. Assuming Artin’s conjecture, there are infinitely many such k for any prime q.

Coded computation is an emerging paradigm of applying coding theory to large-scale distributed computing to provide resilience against slow or otherwise unavailable workers. We propose a new approach to view coded computation via the lens of the locality of codes. We do so by defining a new notion of locality, calledcomputational locality, using the locality properties of an appropriately defined code for the function being computed. This notion of locality incorporates the unique aspects of locality arising in the context of coded computation. Our first major contribution is to demonstrate how to design a coded computation scheme for a function using the local recovery scheme of an appropriately defined code. The so-obtained scheme rederives the best known coded computation scheme for multivariate polynomial functions via the viewpoint of the locality of the Reed-Muller code. Our second major contribution is to show that the proposed locality-based approach enables new tradeoffs (e.g., communication bandwidth vs number of workers) compared to existing coded computation schemes. Specifically for the case when there is known linear dependence among inputs—common in many real-world applications—the proposed approach significantly reduces resource overhead (i.e., number of workers) without incurring any tradeoffs.

Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code $\mathcal{G}$ so that, given a noisy version of the encoding $\mathcal{G}(j)$ of an integer $j$, one can recover $\hat{j}$ that is close to $j$ (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code $\mathcal{G}$ of rate $1 - H_2(p) - \varepsilon$ that is efficiently encodable, and that is robust in the following sense. Supposed that $\mathcal{G}(j)$ is passed through the binary symmetric channel $\text{BSC}_p$ with cross-over probability $p$, to obtain $x$. We present an efficient decoding algorithm that, given $x$, returns an estimate $\hat{j}$ so that $|j - \hat{j}|$ is small with high probability.

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and a set {D}subseteq V x V of k demand pairs. The aim is to compute the cheapest network N subseteq G for which there is an s -> t path for each (s,t)in {D}. It is known that this problem is notoriously hard as there is no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k. For the bi-DSN_Planar problem, the aim is to compute a planar optimum solution N subseteq G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of bi-DSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of bi-DSN_Planar and obtain upper and lower bounds on obtainable runtimes parameterized by k. One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network N subseteq G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2-{epsilon})-approximation algorithm parameterized by k (for any epsilon>0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.

We study the problem of robust multivariate polynomial regression: let $p\colon\mathbb{R}^n\to\mathbb{R}$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ that are noisy versions of $(\mathbf{x}_i,p(\mathbf{x}_i))$. More precisely, each $\mathbf{x}_i$ is sampled independently from some distribution $χ$ on $[-1,1]^n$, and for each $i$ independently, $y_i$ is arbitrary (i.e., an outlier) with probability at most $ρ< 1/2$, and otherwise satisfies $|y_i-p(\mathbf{x}_i)|\leqσ$. The goal is to output a polynomial $\hat{p}$, of degree at most $d$ in each variable, within an $\ell_\infty$-distance of at most $O(σ)$ from $p$. Kane, Karmalkar, and Price [FOCS'17] solved this problem for $n=1$. We generalize their results to the $n$-variate setting, showing an algorithm that achieves a sample complexity of $O_n(d^n\log d)$, where the hidden constant depends on $n$, if $χ$ is the $n$-dimensional Chebyshev distribution. The sample complexity is $O_n(d^{2n}\log d)$, if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most $O(σ)$, and the run-time depends on $\log(1/σ)$. In the setting where each $\mathbf{x}_i$ and $y_i$ are known up to $N$ bits of precision, the run-time's dependence on $N$ is linear. We also show that our sample complexities are optimal in terms of $d^n$. Furthermore, we show that it is possible to have the run-time be independent of $1/σ$, at the cost of a higher sample complexity.

We prove that a binary linear code of block length$n$that is locally correctable with 3 queries against a fraction$\delta > 0$of adversarial errors must have dimension at most$o_{\delta} ( >\log^{2}n$. log log$n$). This is almost tight in view of quadratic Reed-Muller codes being a 3-query locally correctable code (LCC) with dimension$\Theta^{-}(\log^{2}n)$. Our result improves, for the binary field case, the$O_{\delta}(\text{lo}\overline{\mathrm{g}}^{8}n)$bound obtained in the recent breakthrough of [1] (and the more recent improvement to$O_{\delta}(\log^{4}n)$for binary linear codes announced in [2]). Previous bounds for 3-query linear LCCs proceed by constructing a 2-query locally decodable code (LDC) from the 3-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [3]. That is, we show that if$x\rightarrow(v_{1}\cdot x,\ v_{2}\cdot x,\ \ldots,\ v_{n}\cdot x)$is an arbitrary encoding map$\mathbb{F}_{2}^{k}\rightarrow \mathbb{F}_{\underline{2}}^{n}$for the 3-query LCC, then all vectors in$\mathbb{F}_{2}^{k}$can be written as a$O_{\delta}(\log n)$-sparse linear com-bination of the$v_{i}{\prime}s$, which immediately implies$\overline{k}\leq\overline{O}_{\delta}((\log n)^{2})$. The proof of this fact proceeds by iteratively∼reducing the size of any arbitrary linear combination of at least$\Omega_{\delta}(\log n)$of the$v_{i}{\prime}s$. We achieve this using the recent breakthrough result of [4] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.

Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.

We consider the task of certifying that a random d-dimensional subspace X in$\mathbb{R}^{\gamma}$is well-spread - every vec-tor$\chi\in X$satisfies$c\sqrt{n}\Vert x\Vert_{2}\leq\Vert x\Vert_{1}\leq\sqrt{n}^{-}\Vert x\Vert_{2}$. In a seminal work, Barak et. al. [3] showed a polynomial-time certification algorithm when$d\leqslant O(\sqrt{n})$. On the other hand, when$d \gg \sqrt{n} r$the certification task is information-theoretically possible but there is evidence that it is computationally hard [10], [39], a phenomenon known as the information-computation gap. In this paper, we give sub exponential-time certification algorithms in the$d \ll \sqrt{n}$regime. Our algorithm runs in time$\exp(\tilde{O}(n^{\varepsilon}))$when$\dot{d} \leqslant \widetilde{O}\left(n^{\frac{1+\varepsilon}{2}}\right)$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.

Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage of soft information. In this paper, we propose the successive cancellation sampling (SCS) decoder. SCS hires iid “agents” to sample codewords using posterior probabilities. This makes it fully parallel and amenable for some theoretical analysis. As an example, when comparing SCS with$\boldsymbol{a}$agents to any list decoder with list size$\boldsymbol{\ell}$, we can prove that the error probability of the former is at most$\boldsymbol{\ell}/\boldsymbol{ae}$more than that of the latter. In this paper, we also describe how to adjust the “temperature” of agents. Warmer agents are less likely to sample the same codewords and hence can further reduce error probability.

Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adaptive; the latter is preferred when latency is ess of an issue. To construct adaptive GT schemes, a popular strategy is to spend the majority of tests in the first few rounds to gain as much information as possible, and uses later rounds to refine details. In this paper, we propose a transparent strategy called isolate and then identify (I@I). In the first few rounds, I@I divides the population into teams until every team contains at most one sick person. Then, in the last round, I@I identifies the sick person in each team. Performance-wise, I@I is the first GT scheme that achieves the optimal coefficient 1/capacity(Z) for the$k\log_{2}(n/k)$term in the number of tests when$\boldsymbol{Z}$is a generic channel corrupting the test outcomes. I@I follows a modular methodology whereby the isolating part and the identification part can be optimized separately.

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate R codes are not list-decodable using list-size L beyond an error fraction (the Singleton bound being the case of L = 1, i.e., unique decoding). We prove that in order to approach this bound for any fixed L > 1, one needs exponential alphabets. Specifically, for every L > 1 and R ∈ (0,1), if a rate R code can be list-of-L decoded up to error fraction , then its alphabet must have size at least exp(ΩL,R(1/ɛ)). This is in sharp contrast to the situation for unique decoding where certain families of rate R algebraic-geometry (AG) codes over an alphabet of size O(1/ɛ2) are unique-decodable up to error fraction (1 — R — ɛ)/2.

Reed–Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed–Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam, established that Reed–Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed–Solomon codes over an exponentially large field size 2O(n), where n is the block length of the code. A natural question is whether Reed–Solomon codes can still achieve capacity over smaller fields. Recently, Guo and Zhang showed that Reed–Solomon codes are list-decodable to capacity with field size O(n2). We show that Reed–Solomon codes are list-decodable to capacity with linear field size O(n), which is optimal up to the constant factor. We also give evidence that the ratio between the alphabet size q and code length n cannot be bounded by an absolute constant. Our techniques also show that random linear codes are list-decodable up to (the alphabet-independent) capacity with optimal list-size O(1/ε) and near-optimal alphabet size 2O(1/ε2), where ε is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O(1/ε) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. Our proofs are based on the ideas of Guo and Zhang, and we additionally exploit symmetries of reduced intersection matrices. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

Abstract. We prove that the minimum distance problem ([Formula: see text]) on linear codes over any fixed finite field and parameterized by the input distance bound is [Formula: see text]-hard to approximate within any constant factor. We also prove analogous results for the parameterized shortest vector problem ([Formula: see text]) on integer lattices. Specifically, we prove that the [Formula: see text] in the [Formula: see text] norm is [Formula: see text]-hard to approximate within any constant factor for any fixed [Formula: see text] and [Formula: see text]-hard to approximate within a factor approaching 2 for [Formula: see text]. (We show hardness under randomized reductions in each case.) These results answer the main questions left open (and explicitly posed) by Bhattacharyya et al. [ J. ACM, 68 (2021), 16] on the complexity of the parameterized [Formula: see text] and [Formula: see text]. For the [Formula: see text], they established similar hardness for binary linear codes and left the case of general fields open. For the [Formula: see text] in [Formula: see text] norms with [Formula: see text], they showed inapproximability within some constant factor (depending on [Formula: see text]) and left open showing such hardness for arbitrary constant factors. They also left open showing [Formula: see text]-hardness even of the exact SVP in the [Formula: see text] norm.

We present an explicit construction of a sequence of rate $1/2$ Wozencraft ensemble codes (over any fixed finite field $\mathbb{F}_q$) that achieve minimum distance $Ω(\sqrt{k})$ where $k$ is the message length. The coefficients of the Wozencraft ensemble codes are constructed using Sidon Sets and the cyclic structure of $\mathbb{F}_{q^{k}}$ where $k+1$ is prime with $q$ a primitive root modulo $k+1$. Assuming Artin's conjecture, there are infinitely many such $k$ for any prime power $q$.

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst case and average case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^{*}$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution “shifted by $x^{*}$” so that $x^{*}$ satisfies each constraint. For an n variable semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}\left(n^{k / 2}\right)$ constraints. This matches, up to ${\mathrm {polylog}} (n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [23], as well as algorithms that refute random and semirandom CSPs [1], [4]. Our result shows that despite having worst case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst case, where analogous results require $O\left(n^{k}\right)$ constraints [7], [26]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices — reminiscent of the classical spectral sparsification — which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works (Saket, NeurIPS'21; Saket, NeurIPS'22) which showed algorithms and hardness for learning halfspaces in the LLP setting. In this work we focus on the intractability of LLP learning Boolean functions. Our first result shows that given a collection of bags of size at most $2$ which are consistent with an OR function, it is NP-hard to find a CNF of constantly many clauses which satisfies any constant-fraction of the bags. This is in contrast with the work of (Saket, NeurIPS'21) which gave a $(2/5)$-approximation for learning ORs using a halfspace. Thus, our result provides a separation between constant clause CNFs and halfspaces as hypotheses for LLP learning ORs. Next, we prove the hardness of satisfying more than $1/2 + o(1)$ fraction of such bags using a $t$-DNF (i.e. DNF where each term has $\leq t$ literals) for any constant $t$. In usual PAC learning such a hardness was known (Khot-Saket, FOCS'08) only for learning noisy ORs. We also study the learnability of parities and show that it is NP-hard to satisfy more than $(q/2^{q-1} + o(1))$-fraction of $q$-sized bags which are consistent with a parity using a parity, while a random parity based algorithm achieves a $(1/2^{q-2})$-approximation.

The tail latency of large-scale distributed computations, such as matrix multiplication, is adversely affected by unavailable workers. A technique called "coded computation" alleviates this problem by using extra workers to evaluate the function being computed at coded inputs and substitute the extra workers for the unavailable ones. Most of the literature on coded computation of multivariate polynomials applies to arbitrary inputs and ignores the structure of the inputs. However, a recent work introduced a locality-based coded computation framework and showed how to leverage the structure of inputs to reduce the overhead of coded computation. Our work expands the toolkit of locality-based approaches to coded computation beyond linearly dependent input points for the class of m-homogeneous polynomials. Specifically, we present new methods to exploit the structure of each coordinate of the inputs. Finally, we apply our new tools to multiplying upper (or lower) triangular matrices and show a reduction in the number of workers needed compared to the best known coded computation schemes.

Polar codes that approach capacity at a near-optimal speed, namely with scaling exponents close to 2, have been shown possible for q-ary erasure channels (Pfister and Urbanke), the BEC (Fazeli, Hassani, Mondelli, and Vardy), all BMS channels (Guruswami, Riazanov, and Ye), and all DMCs (Wang and Duursma). There is, nevertheless, a subtlety separating the last two papers from the first two, namely the usage of multiple dynamic kernels in the polarization process, which leads to increased complexity and fewer opportunities to hardware-accelerate. This paper clarifies this subtlety, providing a tradeoff between the number of kernels in the construction and the scaling exponent. We show that the number of kernels can be bounded by O(ℓ3/µ−1) where µ is the targeted scaling exponent and ℓ is the kernel size. In particular, if one settles for scaling exponent approaching 3, a single kernel suffices, and to approach the optimal scaling exponent of 2, about $O(\sqrt \ell )$ kernels suffice.

We modify Price and Scarlett’s fast binary splitting approach to nonadaptive group testing [1]. We show that, to identify a uniformly random subset of k infected persons among a population of n, it takes only ln(2−4ε)−2k ln n tests and decoding complexity O(ε−2k ln n), for any small ε > 0, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use ln(2)−2k ln n or fewer tests require linear-in-n complexity, sometimes even polynomial in n; those that enjoy sub-n complexity employ O(k ln n) tests, where the big-O scalar is implicit, presumably greater than ln(2)−2. We almost achieve the best of both worlds, namely, the almost-ln(2)−2scalar and the sub-n decoding complexity. How much further one can reduce the scalar ln(2)−2remains an open problem.

A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that SVP in the ℓp norm is W[1]-hard to approximate within any constant factor for any fixed p >1 and W[1]-hard to approximate within a factor approaching 2 for p=1. (We show hardness under randomized reductions in each case.)

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.

In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if ≈ 1/3 of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding 1/4.

Abstract. We study the problem of computing the [Formula: see text] norm of a matrix [Formula: see text], defined as [Formula: see text]. This problem generalizes the spectral norm of a matrix ([Formula: see text]) and the Grothendieck problem ([Formula: see text], [Formula: see text]) and has been widely studied in various regimes. When [Formula: see text], the problem exhibits a dichotomy: constant factor approximation algorithms are known if [Formula: see text], and the problem is hard to approximate within almost polynomial factors when [Formula: see text]. The regime when [Formula: see text], known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case with [Formula: see text] and [Formula: see text] was studied by Barak et al. [ Proceedings of the 44 th Annual ACM Symposium on Theory of Computing, 2012, pp. 307–326], who gave subexponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the exponential time hypothesis. However, no NP-hardness of approximation is known for these problems for any [Formula: see text]. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any [Formula: see text] with [Formula: see text], [Formula: see text] is hard to approximate within [Formula: see text] assuming [Formula: see text]. En route to the above result, we also prove almost tight results for the case when [Formula: see text] with [Formula: see text].

Abstract. This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are limited to having an information rate at most [Formula: see text] (achieved by the trivial two fold repetition code). Previously, it was (erroneously) reported that more generally no nontrivial linear codes correcting [Formula: see text] deletions exist, i.e., that the [Formula: see text]-fold repetition codes and its rate of [Formula: see text] are basically optimal for any [Formula: see text]. We disprove this and show the existence of binary linear codes of length [Formula: see text] and rate just below [Formula: see text] capable of correcting [Formula: see text] insertions and deletions. This identifies rate [Formula: see text] as a sharp threshold for recovery from deletions for linear codes and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically good linear code for Hamming errors into an asymptotically good linear code for insdel errors. Last, we show that the [Formula: see text]-rate limitation does not hold for affine codes by giving an explicit affine code of rate [Formula: see text] which can efficiently correct a constant fraction of insdel errors.

We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations: 1) We construct linear-time encodable and decodable length-$n$non-binary codes correcting a single edit error with nearly optimal redundancy$\log n+O(\log \log n)$, providing an alternative simpler proof of a result by Cai et al. (IEEE Trans. Inf. Theory 2021). This is achieved by employing what we call weighted VT sketches, a new notion that may be of independent interest. 2) We show the existence of a binary code correcting one deletion or one adjacent transposition with nearly optimal redundancy$\log n+O(\log \log n)$. 3) We construct linear-time encodable and list-decodable binary codes with list-size 2 for one deletion and one substitution with redundancy$4\log n+O(\log \log n)$. This matches the Gilbert-Varshamov existential bound up to an$O(\log \log n)$additive term.

We prove that there exists an absolute constant$\delta >0$such that any binary code$C\subset \{0,1\}^{N} \vphantom {_{\int }}$tolerating$(1/2-\delta)N$adversarial deletions must satisfy$|C|\le 2^{ \mathop {\mathrm {poly}} \log N}$and thus have rate asymptotically approaching 0. This is the first 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$C\subset \{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+2\delta)/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.

Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.

We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations: - We construct linear-time encodable and decodable length-n non-binary codes correcting a single edit error with nearly optimal redundancy log n+O(log log n), providing an alternative simpler proof of a result by Cai, Chee, Gabrys, Kiah, and Nguyen (IEEE Trans. Inf. Theory 2021). This is achieved by employing what we call weighted VT sketches, a new notion that may be of independent interest. - We show the existence of a binary code correcting one deletion or one adjacent transposition with nearly optimal redundancy log n+O(log log n). - We construct linear-time encodable and list-decodable binary codes with list-size 2 for one deletion and one substitution with redundancy 4log n+O(log log n). This matches the existential bound up to an O(log log n) additive term.

Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices. Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes. On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.

Random linear codes are a workhorse in coding theory, and are used to show the existence of codes with the best known or even near-optimal trade-offs in many noise models. However, they have little structure besides linearity, and are not amenable to tractable error-correction algorithms. In this work, we prove a general derandomization result applicable to random linear codes. Namely, in settings where the coding-theoretic property of interest is “local” (in the sense of forbidding certain bad configurations involving few vectors–code distance and list-decodability being notable examples), one can replace random linear codes (RLCs) with a significantly derandomized variant with essentially no loss in parameters. Specifically, instead of randomly sampling coordinates of the (long) Hadamard code (which is an equivalent way to describe RLCs), one can randomly sample coordinates of any code with low bias. Over large alphabets, the low bias requirement can be weakened to just large distance. Furthermore, large distance suffices even with a small alphabet in order to match the current best known bounds for RLC list-decodability. In particular, by virtue of our result, all current (and future) achievability bounds for list-decodability of random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) “mother” code. We also show that our punctured codes emulate the behavior of RLCs on stochastic channels, thus giving a derandomization of RLCs in the context of achieving Shannon capacity as well. Thus, we have a randomness-efficient way to sample codes achieving capacity in both worst-case and stochastic settings that can further inherit algebraic or other algorithmically useful structural properties of the mother code. This is an extended abstract. The full version is available at https://arxiv.org/abs/2109.11725.

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 who proposed a hypergraph version of this conjecture, and also studied its implied fractional versions. We establish the fractional version of the Aharoni-Zerbib conjecture up to lower order terms. Specifically, we give a factor approximation based on LP rounding for an algorithmic version of the hypergraph Turán problem (AHTP). The objective in AHTP is to pick the smallest collection of (t–1)-sized subsets of vertices of an input t-uniform hypergraph such that every hyperedge contains one of these subsets. Aharoni and Zerbib also posed whether Tuza's conjecture and its hypergraph versions could follow from non-trivial duality gaps between vertex covers and matchings on hypergraphs that exclude certain sub-hypergraphs, for instance, a “tent” structure that cannot occur in the incidence of triangles and edges. We give a strong negative answer to this question, by exhibiting tent-free hypergraphs, and indeed ℱ-free hypergraphs for any finite family ℱ of excluded sub-hypergraphs, whose vertex covers must include almost all the vertices. The algorithmic questions arising in the above study can be phrased as instances of vertex cover on simple hypergraphs, whose hyperedges can pairwise share at most one vertex. We prove that the trivial factor t approximation for vertex cover is hard to improve for simple t-uniform hypergraphs. However, for set cover on simple n-vertex hypergraphs, the greedy algorithm achieves a factor (ln n)/2, better than the optimal ln n factor for general hypergraphs.

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 the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(ℓ) 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 Õ(n) (n/ell)^(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.

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of polynomials over $${\mathbb {F}}_2$$ each of which is a product of affine forms. We focus on the case of k-CNF formulas (the $${k}-\textsc {Sub}-\textsc {Sat}$$ problem). Clearly, $${k}-\textsc {Sub}-\textsc {Sat}$$ is no easier than k-SAT, and might be harder. Indeed, via simple reductions we show that $${2}-\textsc {Sub}-\textsc {Sat}$$ is NP-hard, and $${\small \mathrm {W}}[1]$$ -hard when parameterized by the co-dimension of the subspace. We also prove that the optimization version Max- $${2}-\textsc {Sub}-\textsc {Sat}$$ is NP-hard to approximate better than the trivial 3/4 ratio even on satisfiable instances. On the algorithmic front, we investigate fast exponential algorithms which give non-trivial savings over brute-force algorithms. We give a simple branching algorithm with running time $$O^*(1.5)^r$$ for $${2}-\textsc {Sub}-\textsc {Sat}$$ , where r is the subspace dimension, as well as an $$O^*(1.4312)^n$$ time algorithm where n is the number of variables. Turning to $${k}-\textsc {Sub}-\textsc {Sat}$$ for $$k \geqslant 3$$ , while known algorithms for solving a system of degree k polynomial equations already imply a solution with running time $$\approx 2^{r(1-1/2k)}$$ , we explore a more combinatorial approach. Based on an analysis of critical variables (a key notion underlying the randomized k-SAT algorithm of Paturi, Pudlak, and Zane), we give an algorithm with running time $$\approx {n\atopwithdelims (){\leqslant t}} 2^{n-n/k}$$ where n is the number of variables and t is the co-dimension of the subspace. This improves upon the running time of the polynomial equations approach for small co-dimension. Our combinatorial approach also achieves polynomial space in contrast to the algebraic approach that uses exponential space. We also give a PPZ-style algorithm for $${k}-\textsc {Sub}-\textsc {Sat}$$ with running time $$\approx 2^{n-n/2k}$$ . This algorithm is in fact oblivious to the structure of the subspace, and extends when the subspace-membership constraint is replaced by any constraint for which partial satisfying assignments can be efficiently completed to a full satisfying assignment. Finally, for systems of O(n) polynomial equations in n variables over $${\mathbb {F}}_2$$ , we give a fast exponential algorithm when each polynomial has bounded degree irreducible factors (but can otherwise have large degree) using a degree reduction trick.

We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1-R-ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The alphabet size depends only ε and is nearly optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield . In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice “periodic” structure. To prune this subspace and obtain a good bound on the list size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets that are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspace-evasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e.) sets that leads to excellent list size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs , which were subsequently constructed explicitly and also found further applications in pseudorandomness. To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia–Stichtenoth tower of function fields. Combining this with pruning via h.s.e. sets yields codes list-decodable up to a 1-R-ε error fraction with list size bounded by O (1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made exp ( Õ (1/ε 2 )), which is not much worse than the lower bound of exp (Ω (1/ε)). The parameters we achieve are thus quite close to the existential bounds in all three aspects (error-correction radius, alphabet size, and list size) simultaneously. This construction is, however, Monte Carlo and the claimed list-decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O _ε ( N c ) for an absolute constant c , where N is the code’s block length. Using subspace designs instead for the pruning, our approach yields the first deterministic construction of an algebraic code family of rate R with efficient list decoding from 1-R-ε fraction of errors over an alphabet of constant size exp (Õ(1/ε 2 )). The list-size bound is upper bounded by a very slowly growing function of the block length N ; in particular, it is at most O(log ( r ) N ) (the r th iterated logarithm) for any fixed integer r . The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size.

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$(n,r,h,a,q)$-Local Reconstruction Code (LRC) 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$’ erasures 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 ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically 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$h \leqslant 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.

A family of error-correcting codes is list-decodable from error fraction$p$if, for every code in the family, the number of codewords in any Hamming ball of fractional radius$p$is less than some integer$L$. It is said to be list-recoverable for input list size$\ell $if for every sufficiently large subset of at least$L$codewords, there is a coordinate where the codewords take more than$\ell $values. In this work, we study the list size ofrandom linear codesfor both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below$q$is the alphabet size, and$ \varepsilon > 0$is the gap to capacity). (1) A random linear code of rate$1 - \log _{q}(\ell) - \varepsilon $requires list size$L \ge \ell ^{\Omega (1/ \varepsilon)}$for list-recovery from input list size$\ell $. (2) A random linear code of rate$1 - h_{q}(p) - \varepsilon $requires list size$L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $for list-decoding from error fraction$p$. (3) A randombinarylinear code of rate$1 - h_{2}(p) - \varepsilon $is list-decodable fromaverageerror fraction$p$with list size with$L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).

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^{\ast}$is thethreshold ratefor$\mathcal {P}$if a random code of rate$R^{\ast} + \varepsilon $is very likely to satisfy$\mathcal {P}$, while a random code of rate$R^{\ast} - \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 factequalto 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 forlist-recoveryin general.

Let$W$be a binary-input memoryless symmetric (BMS) channel with Shannon capacity$I(W)$and fix any$\alpha > 0$. We construct, for any sufficiently small$\delta > 0$, binary linear codes of block length$O(1/\delta ^{2+\alpha })$and rate$I(W)-\delta $that enable reliable communication on$W$with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established theexistenceof such codes (without efficient constructions or decoding) with block length$O(1/\delta ^{2})$. This quadratic dependence on the gap$\delta $to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

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 visible rank. The locality constraints of a linear code are stipulated by a matrix H of ⋆’s and 0’s (which we call a "stencil"), whose rows correspond to the local parity checks (with the ⋆’s indicating the support of the check). The visible rank of H is the largest r for which there is a r × r submatrix in H with a unique generalized diagonal of ⋆’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 point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [Zeev Dvir et al., 2020]. Using this connection and a construction of appropriate stencils, we answer a question posed in [Zeev Dvir et al., 2020] and demonstrate that symmetric spanoid rank cannot improve the currently best known Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-query locally correctable codes (LCCs) of length n. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs. 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 codes with 2-DRGP must have co-dimension Ω(√n) (which is matched by a simple product code construction). 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 Ω(n), thus recovering the Ω(√n) lower bound for 2-DRGP. For q-LCC, however, the k'th tensor power for k ⩽ n^{o(1)} is unable to improve the Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-LCCs by a polynomial factor.Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.

We prove that there exists an absolute constant 6 > 0 such any binary code$C$⊂ {0, 1}Ntolerating (1/2 - δ)$N$adversarial deletions must satisfy| C| ≤ 2polylog$N$and thus have rate asymptotically approaching 0. This is the first 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 6 > 0 such that any set$C$⊂ {0, 1} of 2logAN binary strings must contain two strings$c$and c’ whose longest common subsequence has length at least (1/2 + δ) N. As an immediate corollary, we show that q-ary codes tolerating a fraction 1 - (1 + 2δ) /$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.

Consider an expander graph in which a $μ$ fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman showed in 1993 that the number of marked vertices seen in a random walk of length $n$ is concentrated around its expectation, $Φ:= μn$, independent of the size of the graph. Here we provide a new and sharp tail bound, improving on the existing bounds whenever $μ$ is not too large.

Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂ Σⁿ. For example, for some p ∈ (0,1), 𝒫 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 𝒫 if a random code of rate R^* + ε is very likely to satisfy 𝒫, while a random code of rate R^* - ε is very unlikely to satisfy 𝒫. 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 𝒫 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.

The Shannon capacity of a graph is a fundamental quantity in zero-error information theory measuring the rate of growth of independent sets in graph powers. Despite being well-studied, this quantity continues to hold several mysteries. Lovász famously proved that the Shannon capacity of$C$5(the 5-cycle) is at most$\sqrt{5}$via his theta function. This bound is achieved by a simple linear code over$\mathbb{F}_{5}$mapping x → 2x. This motivates the notion of linear Shannon capacity of graphs, which is the largest rate achievable when restricting oneself to linear codes. We give a simple proof based on the polynomial method that the linear Shannon capacity of$C$5is$\sqrt{5}$. Our method applies more generally to Cayley graphs over the additive group of finite fields$\mathbb{F}_{q}$, giving an upper bound on the linear Shannon capacity. We compare this bound to the Lovász theta function, showing that they match for self-complementary Cayley graphs (such as C5), and that the bound is smaller in some cases. We also exhibit a quadratic gap between linear and general Shannon capacity for some graphs.

We revisit the linear programming bounds for the size vs. distance trade-off for binary codes, focusing on the bounds for the almost-balanced case, when all pairwise distances are between$d$and$n-d$, where$d$is the code distance and$n$is the block length. We give an optimal solution to Delsarte's LP for the almost-balanced case with large distance$d\geq(n-\sqrt{n})/2+1$, which shows that the optimal value of the LP coincides with the Grey-Rankin bound for self-complementary codes. We also show that a limitation of the asymptotic LP bound shown by Samorodnitsky, namely that it is at least the average of the first MRRW upper bound and Gilbert-Varshamov bound, continues to hold for the almost-balanced case.

Coded computation is an emerging paradigm for robustness in large-scale distributed computing, which applies principles from coding theory to provide robustness against slow or otherwise unavailable workers. We propose a new approach to view coded computation via the lens of locality of codes. We do so by defining a new notion of locality, called computational locality, via the locality properties of an appropriately defined code for the function being computed. This notion of locality incorporates the unique aspects of locality arising in the context of coded computation. Using this new approach, (1) We demonstrate how to design a coded computation scheme for a function using the local decoding scheme of an appropriately defined code. This rederives the best-known coded computation scheme for multivariate polynomial functions via the viewpoint of locality of the Reed Muller code. (2) We show that the proposed locality-based approach enables coded computation schemes with significantly lower resource overhead than existing schemes. Specifically, matrix multiplication over complex numbers, a common workload in high performance computing, is achieved with 33.3% fewer workers than state-of-the-art coded computation schemes.

We give an efficient algorithm to strongly refute 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 efficient 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 Õ(nk/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 not pseudorandom) and reducing it to a partitioned collection of 2-XOR instances. We analyze these subinstances using a carefully chosen quadratic form as 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.

This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are limited to have information rate at most 1/2 (achieved by the trivial 2-fold repetition code). Previously it was (erroneously) reported that more generally no non-trivial linear codes correcting k deletions exist, i.e., that the (k + 1)-fold repetition codes and its rate of 1/(k + 1) are basically optimal for any k. We disprove this and show the existence of binary linear codes of length n and rate just below 1/2 capable of correcting Ω(n) insertions and deletions. This identifies rate 1/2 as a sharp threshold for recovery from deletions for linear codes, and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically-good linear code for Hamming errors into an asymptotically-good linear code for insdel errors. Lastly we show that the ½-rate limitation does not hold for affine codes by giving an explicit affine code of rate 1 – ∊ which can efficiently correct a constant fraction of insdel errors.

We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2n/n4). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Ω(2n/n3+o(1)) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

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.

An$(n,k,\ell)$-vector MDS code over a field$\mathbb {F}$is a$\mathbb {F}$-linear subspace of$(\mathbb {F}^\ell)^{n}$of dimension$k\ell $, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell $of each codeword symbol is called thesub-packetizationof the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading$\ell /r$field elements (which is known to be the minimum possible) from each of the other symbols. MSR codes are attractive for use in distributed storage systems, and by now a variety of ingenious constructions of MSR codes are available. However, they all suffer from exponentially large sub-packetization$\ell \gtrsim r^{k/r}$. Our main result is an almost tight lower bound showing that for an MSR code, one must have$\ell \geqslant \exp (\Omega (k/r))$. Previously, a lower bound of$\approx \exp (\sqrt {k/r})$, and a tight lower bound for a restricted class of “optimal access” MSR codes, were known.

We give an explicit construction of length- n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2n/n4). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Ω(2n/n3+o(1)) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by$q$-ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a$\gamma \leq 0.707$fraction of insertions is tolerable by some binary code family. For any desired$\varepsilon > 0$, we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of$\gamma $fraction of insertions and$\delta $fraction of deletions as long as$\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any$\gamma, \delta $with$\gamma + 2\delta = 1$list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size$q$. Surprisingly, our work reveals that the feasibility region for$q>2$isnotthe natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a$(q-1)$-piece-wise linear boundary whose$q$corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently largesizewith good list-decoding properties for any combination of$\delta,\gamma $within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate.

Dinur’s celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the expense of a fixed constant factor loss in the soundness gap). We note that the gap amplification can produce a Label Cover CSP. This allows us to reduce the alphabet size via a direct long-code based reduction from Label Cover to a Boolean CSP. Our composition step thus bypasses the concept of Assignment Testers from Dinur’s proof, and we believe it is more intuitive - it is just a gadget reduction. The analysis also uses only elementary facts (Parseval’s identity) about Fourier Transforms over the hypercube.

The d-to-1 conjecture of Khot asserts that it is NP-hard to satisfy an ε fraction of constraints of a satisfiable d-to-1 Label Cover instance, for arbitrarily small ε > 0. We prove that the d-to-1 conjecture for any fixed d implies the hardness of coloring a 3-colorable graph with C colors for arbitrarily large integers C. Earlier, the hardness of O(1)-coloring a 4-colorable graphs is known under the 2-to-1 conjecture, which is the strongest in the family of d-to-1 conjectures, and the hardness for 3-colorable graphs is known under a certain "fish-shaped" variant of the 2-to-1 conjecture.

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.

Let W be a binary-input memoryless symmetric (BMS) channel with Shannon capacity I(W) and fix any α > 0. We construct, for any sufficiently small δ > 0, binary linear codes of block length O(1/δ2+α) and rate I(W)−δ that enable reliable communication on W with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length O(1/δ2). This quadratic dependence on the gap δ to capacity is known to be the best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the binary erasure channel.

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.

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When $r=k$ (the maximum possible value), i.e., the hypergraph is $k$-partite, one can efficiently $2$-rainbow color the hypergraph, i.e., $2$-color its vertices so that there are no monochromatic edges. In this work, we consider the next smaller value of $r=k-1$ and prove that in this case it is NP-hard to rainbow color the hypergraph with $q := \lceil \frac{k-2}{2} \rceil$ colors. In particular, for $k \le 6$, it is NP-hard to $2$-color $(k-1)$-rainbow colorable $k$-uniform hypergraphs. Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set $[r]^n$. We prove that any such polymorphism $f: [r]^n \to [q]$ must be $C$-fixing, i.e., there are a small subset $S$ of $C$ coordinates and a setting $a \in [q]^S$ such that fixing $x_{|S} = a$ determines the value of $f(x)$. The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the $C$-fixing characterization, our NP-hardness is obtained via a reduction from smooth Label Cover.

We prove a new upper bound on the size of codes C ⊆ {1, 2, 3, 4}nwith the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we provide a self-contained proof that such codes have size at most 26n/19+o(n), that is, rate bounded asymptotically by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlós, 1984) and (Körner and Marton, 1988). Finally, using a combination of our approach with a simple idea which exploits powerful bounds on the minimum distance of codes in the Hamming space, we further improve the upper bound to 0.31477.

The explosion in the volumes of data being stored online has resulted in distributed storage `s transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. These codes can correct a small number of erasures (which is the typical case) by accessing only a small number of remaining coordinates. An (n, r, h, a, q)-LRC is a linear code over Fqof length n, whose codeword symbols are partitioned into g = n/r local groups each of size r. Each local group has a local parity checks that allow recovery of up to a erasures within the group by reading the unerased symbols in the group. There are a further h “heavy” parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it corrects all erasure patterns which are information-theoretically correctable under the stipulated structure of local and global parity checks, namely patterns with up to a erasures in each local group and an additional h (or fewer) erasures anywhere in the codeword. The existing constructions require fields of size nΩ(h)while no superlinear lower bounds were known for any setting of parameters. Is it possible to get linear field size similar to the related MDS codes (e.g., Reed-Solomon codes)? In this work, we answer this question by showing superlinear lower bounds on the field size of MR-LRCs. When a,h are constant and the number of local groups g ≥ h, while r may grow with n, our lower bound simplifies to q ≥ Ωa,h(n · rmin{a,h-2}) . MR-LRCs deployed in practice have a small number of global parities, typically h = 2, 3 . We complement our lower bounds by giving constructions with small field size for h ≤ 3. When h = 2, we give a linear field size construction, whereas previous constructions required quadratic field size in some parameter ranges. Note that our lower bound is superlinear only if h ≥ 3. When h = 3, we give a construction with O(n3) field size, whereas previous constructions needed nΘ(a)field size. This makes the choices r = 3, a = 1, h = 3 the next simplest non-trivial setting to investigate regarding the existence of MR-LRCs over fields of near-linear size. We answer this question in the positive via a novel approach based on elliptic curves and arithmetic progression free sets.

Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. They have emerged as the codes of choice for large scale distributed storage systems due to the very efficient repair of failed storage nodes in the typical scenario of a single or few nodes failing, while also offering fault tolerance against worst-case scenarios with more erasures. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining p0(adv), the zero-rate threshold of adversarial deletions, defined to be the supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting a fraction p of adversarial deletions. A recent construction of deletion-correcting codes shows that p0(adv)≥ √2 - 1, and the trivial upper bound, p0(adv)≤ 1/2, is the best known. Perhaps surprisingly, we do not know whether or not p0(adv)= 1/2. In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of pn deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction p0(obliv)equals 1. For online 0 deletions, where the channel decides whether to delete bit xibased only on knowledge of bits x1x2. . . xi, define the deterministic zerorate threshold for online deletions p0(on,d)to be the supremum of p for which there exist deterministic codes against an online channel causing pn deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove p0(adv)= 1/2 if and only if p0(on,d)= 1/2.

ϵ-Minimum Storage Regenerating (E-MSR) codes form a special class of Maximum Distance Separable (MDS) codes, providing mechanisms for exact regeneration of a single code block in their codewords by downloading slightly suboptimal amount of information from the remaining code blocks. The key advantage of these codes is a significantly lower subpacketization that grows only logarithmically with the code length, while providing optimality in storage and error-correcting capacity. However, existing constructions of ϵ-MSR codes require each remaining code block to be available for the repair of any failed code block. In this paper, we construct ϵ-MSR codes that can repair any failed code block by contacting fewer number of available code blocks. When a code block fails, our repair procedure needs to contact a few compulsory code blocks and is free to choose any subset of available code blocks for the remaining choices. Our construction requires a field size linear in code length and ensures load balancing (in terms of information downloaded) among the contacted code blocks for repairing a failed code block.

A k-uniform hypergraph is said to be r-rainbow colorable if there is an r-coloring of its vertices such that every hyperedge intersects all r color classes. Given as input such a hypergraph, finding a r-rainbow coloring of it is NP-hard for all k >= 3 and r >= 2. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When r=k (the maximum possible value), i.e., the hypergraph is k-partite, one can efficiently 2-rainbow color the hypergraph, i.e., 2-color its vertices so that there are no monochromatic edges. In this work we consider the next smaller value of r=k-1, and prove that in this case it is NP-hard to rainbow color the hypergraph with q := ceil[(k-2)/2] colors. In particular, for k <=6, it is NP-hard to 2-color (k-1)-rainbow colorable k-uniform hypergraphs. Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set [r]^n. We prove that any such polymorphism f: [r]^n -> [q] must be C-fixing, i.e., there is a small subset S of C coordinates and a setting a in [q]^S such that fixing x_{|S} = a determines the value of f(x). The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the C-fixing characterization, our NP-hardness is obtained via a reduction from smooth Label Cover.

We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by $p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation that can be computed in $O(\log n)$ space. Meanwhile, with high probability, a sample of $\tilde{O}(n)$ constraints suffices to estimate the optimal value to $(1+ε)$ accuracy. We prove that any single-pass streaming algorithm that achieves a $(p-ε)$-approximation requires $Ω_ε(\sqrt{n})$ space. Our proof is via a reduction from lower bounds for a communication problem that is a $p$-ary variant of the Boolean Hidden Matching problem studied in the literature. Given the utility of Unique Games as a starting point for reduction to other optimization problems, our strong hardness for approximating Unique Games could lead to down\emph{stream} hardness results for streaming approximability for other CSP-like problems.

Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an $(n,r,h,a)$-LRC, the $n$ codeword symbols are partitioned into $r$ disjoint groups each of which include $a$ local parity checks capable of locally correcting $a$ erasures. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that exponential in $h$ or $a$, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small $r \ll ε\log n$ and large $h \ge Ω(n^{1-ε})$, we improve the field size from roughly $n^h$ to $n^{εh}$. For the case of $a=1$ (one local parity check), we improve the field size quadratically from $r^{h(h+1)}$ to $r^{h \lfloor (h+1)/2 \rfloor}$ for some range of $r$. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length $\ell$ among any $N \leq 2^\ell$ players such that for a threshold parameter $t$, (i) the knowledge of any $t$ shares does not reveal any information about the secret and, (ii) any choice of $t+1$ shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length $\ell$, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any $t+g$ shares, for a positive integer gap parameter $g$. Ramp secret sharing scheme necessarily requires shares of length $\ell/g$. Other than the bound related to secret length $\ell$, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio $g/N$. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio $g/N$, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any $τ$ fraction of observed shares, and reconstruction from any $ρ$ fraction of shares, for any choices of $0 \leq τ< ρ\leq 1$. Our construction achieves secret length $N(ρ-τ-o(1))$, which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length $Ω(N(ρ-τ))$.

Minimum storage regenerating (MSR) codes are MDS codes which allow for recovery of any single erased symbol with optimal repair bandwidth, based on the smallest possible fraction of the contents downloaded from each of the other symbols. Recently, certain Reed- Solomon codes were constructed which are MSR. However, the sub-packetization of these codes is exponentially large, growing like nΩ(n)in the constant-rate regime. In this work, we study the relaxed notion of ϵ-MSR codes, which incur a factor of (1 + ϵ) higher than the optimal repair bandwidth, in the context of Reed-Solomon codes. We give constructions of constant-rate ϵ-MSR Reed-Solomon codes with polynomial sub-packetization of nO(l/ϵ)and thereby giving an explicit tradeoff between the repair bandwidth and sub-packetization.

We study the problem of computing the p → q operator norm of a matrix A in ℝm×n, defined as ‖A‖p→q : = supx∊ℝn\{0} ‖Ax‖q/‖x‖p. This problem generalizes the spectral norm of a matrix (p = q = 2) and the Grothendieck problem (p = ∞, q = 1), and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 is in [q, p], and the problem is hard to approximate within almost polynomial factors when 2 is not in [q,p]. For the case when 2 is in [q, p] we prove almost matching approximation and NP-hardness results. The regime when p < q, known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by [Barak et. al., STOC’12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 not in [p, q], ‖A‖p→q is hard to approximate within 2O(log1−∊ n) assuming NP is not contained in BPTIME(2logO(1) n)).

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.

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. These codes can correct a small number of erasures (which is the typical case) by accessing only a small number of remaining coordinates. An (n, r, h, a, q)-LRC is a linear code over of length n, whose codeword symbols are partitioned into g = n/r local groups each of size r. Each local group has a local parity checks that allow recovery of up to a erasures within the group by reading the unerased symbols in the group. There are a further h “heavy” parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it corrects all erasure patterns which are information-theoretically correctable under the stipulated structure of local and global parity checks, namely patterns with up to a erasures in each local group and an additional h (or fewer) erasures anywhere in the codeword. The existing constructions require fields of size nΩ(h) while no superlinear lower bounds were known for any setting of parameters. Is it possible to get linear field size similar to the related MDS codes (e.g. Reed-Solomon codes)? In this work, we answer this question by showing superlinear lower bounds on the field size of MR LRCs. When a, h are constant and the number of local groups g  h, while r may grow with n, our lower bound simplifies to MR LRCs deployed in practice have a small number of global parities, typically h = 2, 3 [HSX+12]. We complement our lower bounds by giving constructions with small field size for h  3. When h = 2, we give a linear field size construction, whereas previous constructions required quadratic field size in some parameter ranges. Note that our lower bound is superlinear only if h  3. When h = 3, we give a construction with O(n3) field size, whereas previous constructions needed nΘ(a) field size. Our construction for h = 2 makes the choices r = 3, a = 1, h = 3 the next smallest setting to investigate regarding the existence of MR LRCs over fields of near-linear size. We answer this question in the positive via a novel approach based on elliptic curves and arithmetic progression free sets.

An (n,k,ℓ)-vector MDS code is a F-linear subspace of (Fℓ)n (for some field F) of dimension kℓ, such that any k (vector) symbols of the codeword suffice to determine the remaining r=n−k (vector) symbols. The length ℓ of each codeword symbol is called the Sub-Packetization of the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading ℓ/r field elements (which is known to be the least possible) from each of the other symbols.

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.

In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1 - p)/9, and thus bounded away from 0 for any p0(1- p) for an absolute constant c0> 0.

A locally repairable code (LRC) with locality r allows for the recovery of any erased codeword symbol using only r other codeword symbols. A Singleton-type bound dictates the best possible tradeoff between the dimension and distance of LRCs-an LRC attaining this tradeoff is deemed optimal. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary or, for that matter, even if the alphabet needs to grow at all with the block length. Indeed, for small code distances 3 and 4, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances d ≥ 5, the code length n of an optimal LRC over an alphabet of size q must be at most roughly O(dq3). For the case d = 5, our upper bound is O(q2). We complement these bounds by showing the existence of optimal LRCs of length Ωd,r(q1+1/〈(d-3)/2〉) when d r + 2. These bounds match when d = 5, thus pinning down n = Θ(q2) as the asymptotically largest length of an optimal LRC for this case.

Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily observable from its output), and to decode from Hidden Markov channels (where the channel has a state and the error introduced depends on the state). We give the first polynomial time algorithms that manage to compress and decompress (or encode and decode) at input lengths that are polynomial both in the gap to capacity and the mixing time of the Markov chain. Prior work achieved capacity only asymptotically in the limit of large lengths, and polynomial bounds were not available with respect to either the gap to capacity or mixing time. Our results operate in the setting where the source (or the channel) is known. If the source is unknown then compression at such short lengths would lead to effective algorithms for learning parity with noise - thus our results are the first to suggest a separation between the complexity of the problem when the source is known versus when it is unknown.

A locally repairable code (LRC) with locality $r$ allows for the recovery of any erased codeword symbol using only $r$ other codeword symbols. A Singleton-type bound dictates the best possible trade-off between the dimension and distance of LRCs --- an LRC attaining this trade-off is deemed \emph{optimal}. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary, or for that matter even if the alphabet needs to grow at all with the block length. Indeed, for small code distances $3,4$, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances $d \ge 5$, the code length $n$ of an optimal LRC over an alphabet of size $q$ must be at most roughly $O(d q^3)$. For the case $d=5$, our upper bound is $O(q^2)$. We complement these bounds by showing the existence of optimal LRCs of length $Ω_{d,r}(q^{1+1/\lfloor(d-3)/2\rfloor})$ when $d \le r+2$. These bounds match when $d=5$, thus pinning down $n=Θ(q^2)$ as the asymptotically largest length of an optimal LRC for this case.

For a vector space F^n over a field F, an (eta,beta)-dimension expander of degree d is a collection of d linear maps Gamma_j : F^n -> F^n such that for every subspace U of F^n of dimension at most eta n, the image of U under all the maps, sum_{j=1}^d Gamma_j(U), has dimension at least beta dim(U). Over a finite field, a random collection of d = O(1) maps Gamma_j offers excellent "lossless" expansion whp: beta ~~ d for eta >= Omega(1/d). When it comes to a family of explicit constructions (for growing n), however, achieving even modest expansion factor beta = 1+epsilon with constant degree is a non-trivial goal. We present an explicit construction of dimension expanders over finite fields based on linearized polynomials and subspace designs, drawing inspiration from recent progress on list-decoding in the rank-metric. Our approach yields the following: - Lossless expansion over large fields; more precisely beta >= (1-epsilon)d and eta >= (1-epsilon)/d with d = O_epsilon(1), when |F| >= Omega(n). - Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely beta >= Omega(delta d) and eta >= Omega(1/(delta d)) with d=O_delta(1), when |F| >= n^{delta}. Previously, an approach reducing to monotone expanders (a form of vertex expansion that is highly non-trivial to establish) gave (Omega(1),1+Omega(1))-dimension expanders of constant degree over all fields. An approach based on "rank condensing via subspace designs" led to dimension expanders with beta >rsim sqrt{d} over large fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree.

ε-Minimum Storage Regenerating (ε -MSR) codes form a special class of Maximum Distance Separable (MDS) codes, providing mechanisms for exact regeneration of a single code block in their codewords by downloading slightly suboptimal amount of information from the remaining code blocks. The key advantage of these codes is a significantly lower sub-packetization that grows only logarithmically with the length of the code, while providing optimality in storage and error-correcting capacity. However, from an implementation point of view, these codes require each remaining code block to be available for the repair of any single code block. In this paper, we address this issue by constructing ε -MSR codes that can repair a failed code block by contacting a fewer number of available code blocks. When a code block fails, our repair procedure needs to contact a few compulsory code blocks and is free to choose any subset of a fixed size for the remaining choices (from the available code blocks). Further, our construction requires a field size linear in code length and ensures load balancing among the contacted code blocks in terms of information downloaded from them.

The list-decodability of random linear rank-metric codes is shown to match that of random rank-metric codes. Specifically, an Fq-linear rank-metric code over Fqm×nof rate R=(1-ρ)(1-[n/m]ρ)-ε is shown to be (with high probability) list-decodable up to fractional radius ρ ∈ (0,1) with lists of size at most [(Cp,q)/(ε)], where Cρ,qis a constant depending only on ρ and q. This matches the bound for random rank-metric codes (up to constant factors). The proof adapts the approach of Guruswami, Håstad, Kopparty (STOC 2010), who established a similar result for the Hamming metric case, to the rank-metric setting. A full version of this paper is accessible at https://arxiv.org/abs/1710.11516.

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 binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining p0(adv), the zero-rate threshold of adversarial deletions, defined to be the supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting a fraction p of adversarial deletions. A recent construction of deletion-correcting codes [3] shows that , and the trivial upper bound, p0(adv) ≤ ½, is the best known. Perhaps surprisingly, we do not know whether or not p0(adv) = 1/2. In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of pn deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction p < 1 of oblivious deletions, establishing that the associated zero-rate threshold p0(obliv) equals 1. For online deletions, where the channel decides whether to delete bit xi based only on knowledge of bits x1x2 … xi, define the deterministic zero-rate threshold for online deletions p0(on, d) to be the supremum of p for which there exist deterministic codes against an online channel causing pn deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove p0(adv) = ½ if and only if p0(adv) = ½.

Arikan’s exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2 = ( [complex formula not displayed] ) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization.

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.

This paper addresses the problem of constructing maximum distance separable (MDS) codes that enable exact reconstruction (repair) of each code block by downloading a small amount of information from the remaining code blocks. The total amount of information flow from the remaining code blocks during this reconstruction process is referred to as repair bandwidth of the underlying code. Existing constructions of exact-repairable MDS codes with optimal repair bandwidth require working with large subpacketization levels, which restrict their applicability in practice. This paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required subpacketization level at the cost of slightly suboptimal repair bandwidth. The first approach provides MDS codes that have repair bandwidth at most twice the optimal repair bandwidth. In addition, these codes also have the smallest possible subpacketization level O(r), where r denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair bandwidth at the cost of graceful increment in the required subpacketization level. The second approach transforms an MDS code with optimal repair bandwidth and large subpacketization level into a longer MDS code with small subpacketization level and near-optimal repair bandwidth. For a given r, the codes constructed using this approach have their subpacketization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block.

For an n-variate order-d tensor A, define A_{max} := sup_{||x||_2 = 1} , to be the maximum value taken by the tensor on the unit sphere. It is known that for a random tensor with i.i.d. +1/-1 entries, A_{max} <= sqrt(n.d.log(d)) w.h.p. We study the problem of efficiently certifying upper bounds on A_{max} via the natural relaxation from the Sum of Squares (SoS) hierarchy. Our results include: * When A is a random order-q tensor, we prove that q levels of SoS certifies an upper bound B on A_{max} that satisfies B <= A_{max} * (n/q^(1-o(1)))^(q/4-1/2) w.h.p. Our upper bound improves a result of Montanari and Richard (NIPS 2014) when q is large. * We show the above bound is the best possible up to lower order terms, namely the optimum of the level-q SoS relaxation is at least A_{max} * (n/q^(1+o(1)))^(q/4-1/2). * When A is a random order-d tensor, we prove that q levels of SoS certifies an upper bound B on A_{max} that satisfies B <= A_{max} * (n*polylog/q)^(d/4 - 1/2) w.h.p. For growing q, this improves upon the bound certified by constant levels of SoS. This answers in part, a question posed by Hopkins, Shi, and Steurer (COLT 2015), who tightly characterized constant levels of SoS.

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.

In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data. In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP). This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large---a very strong guarantee---and Locally Recoverable Codes (LRCs) when s is small---a relatively weaker guarantee. This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper. We construct codes in this parameter regime which have a higher rate than previously known codes. Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan. Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.

In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1-p)/9, and thus bounded away from 0 for any p < 1, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate c_0 (1-p) for an absolute constant c_0 > 0.

We study the complexity of estimating the optimum value of a Boolean 2CSP (arity two constraint satisfaction problem) in the single-pass streaming setting, where the algorithm is presented the constraints in an arbitrary order. We give a streaming algorithm to estimate the optimum within a factor approaching 2/5 using logarithmic space, with high probability. This beats the trivial factor 1/4 estimate obtained by simply outputting 1/4-th of the total number of constraints. The inspiration for our work is a lower bound of Kapralov, Khanna, and Sudan (SODA'15) who showed that a similar trivial estimate (of factor 1/2) is the best one can do for Max CUT. This lower bound implies that beating a factor 1/2 for Max DICUT (a special case of Max 2CSP), in particular, to distinguish between the case when the optimum is m/2 versus when it is at most (1/4+eps)m, where m is the total number of edges, requires polynomial space. We complement this hardness result by showing that for DICUT, one can distinguish between the case in which the optimum exceeds (1/2+eps)m and the case in which it is close to m/4. We also prove that estimating the size of the maximum acyclic subgraph of a directed graph, when its edges are presented in a single-pass stream, within a factor better than 7/8 requires polynomial space.

We consider the following basic problem: given an n-variate degree-d homogeneous polynomial f with real coefficients, compute a unit vector x in R̂n that maximizes abs(f(x)). Besides its fundamental nature, this problem arises in diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree-2 case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. We give approximation algorithms for this problem that offer a trade-off between the approximation ratio and running time: in n̂O(q) time, we get an approximation within factor (O(n)/q)̂(d/2-1) for arbitrary polynomials, (O(n)/q)̂(d/4-1/2) for polynomials with non-negative coefficients, and (m /q)̂(1/2) for sparse polynomials with m monomials. The approximation guarantees are with respect to the optimum of the level-q sum-of-squares (SoS) SDP relaxation of the problem (though our algorithms do not rely on actually solving the SDP). Known polynomial time algorithms for this problem rely on “decoupling lemmas.” Such tools are not capable of offering a trade-off like our results as they blow up the number of variables by a factor equal to the degree. We develop new decoupling tools that are more efficient in the number of variables at the expense of less structure in the output polynomials. This enables us to harness the benefits of higher level SoS relaxations. Our decoupling methods also work with “folded polynomials,” which are polynomials with polynomials as coefficients. This allows us to exploit easy substructures (such as quadratics) by considering them as coefficients in our algorithms. We complement our algorithmic results with some polynomially large integrality gaps for d-levels of the SoS relaxation. For general polynomials this follows from known results for random polynomials, which yield a gap of Omega(n)̂(d/4-1/2). For polynomials with non-negative coefficients, we prove an Omega(n̂(1/6) /polylogs) gap for the degree-4 case, based on a novel distribution of 4-uniform hypergraphs. We establish an n̂Omega(d) gap for general degree-d, albeit for a slightly weaker (but still very natural) relaxation. Toward this, we give a method to lift a level-4 solution matrix M to a higher level solution, under a mild technical condition on M. From a structural perspective, our work yields worst-case convergence results on the performance of the sum-of-squareshierarchy for polynomial optimization. Despite the popularity of SoS in this context, such results were previously only known for the case of q = Omega(n).

A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any Q,k >= 2 and \ell <= k/2, given a Qk-uniform hypergraph which admits a k-rainbow coloring satisfying: - in each hyperedge e, for some \ell_e <= \ell all but 2\ell_e colors occur exactly Q times and the rest (Q +/- 1) times, it is NP-hard to compute an independent set of (1 - (\ell+1)/k + \eps)-fraction of vertices, for any constant \eps > 0. In particular, this implies the hardness of even (k/\ell)-rainbow coloring such hypergraphs. The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the k-rainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of \omega(1)-coloring 2-colorable 4-uniform hypergraphs due to Saket, and k-rainbow colorable 2k-uniform hypergraphs due to Guruswami and Lee.

Subspace designs are a (large) collection of high-dimensional subspaces {H_i} of F_q^m such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection with W; more precisely, the sum of dimensions of W cap H_i is at most some parameter L. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F^n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log(log(n)))).

We prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4}nwith the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we show that such a code has size at most 26n/19 +o(n), or equivalently has rate bounded by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlos, 1984) and (Korner and Marton, 1988). The context for this problem is two-fold: zero-error list decoding capacity, where such codes give a way to communicate with no error on the “4/3 channel” when list-of-3 decoding is employed, and perfect hashing, where such codes give a perfect hash family of size n mapping C to {1, 2, 3, 4}.

Minimum storage regenerating (MSR) codes form a special class of maximum distance separable (MDS) codes by providing mechanisms for exact regeneration of a single code block in their codewords by downloading the minimum amount of information from the remaining code blocks. As a result, the MSR codes find application to distributed storage systems to enable node repairs with the optimal repair band-width. However, the construction of exact-repairable MSR codes requires working with a large sub-packetization level, which restricts the employment of these codes in practice. This paper explores exact-repairable MDS codes that significantly reduce the required sub-packetization level by achieving slightly suboptimal repair bandwidth as compared to the MSR codes. This paper presents a general approach to combine an MSR code with large sub-packetization level with a code with large enough minimum distance to construct exact-repairable MDS codes with small sub-packetization level and near-optimal repair bandwidth. For a given number of parity blocks, the codes constructed using this approach have their sub-packetization level scaling logarithmically with the code length. In addition, the obtained codes require field size linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during a node repair.

An (n, M) vector code is a collection of M codewords where n elements (from the field ) in each of the codewords are referred to as code blocks. Assuming that , the code blocks are treated as ℓ-length vectors over the base field . Equivalently, the code is said to have the sub-packetization level ℓ. This paper addresses the problem of constructing MDS vector codes which enable exact reconstruction of each code block by downloading small amount of information from the remaining code blocks. The repair bandwidth of a code measures the information flow from the remaining code blocks during the reconstruction of a single code block. This problem naturally arises in the context of distributed storage systems as the node repair problem [4]. Assuming that , the repair bandwidth of an MDS vector code is lower bounded by ((n — 1)/(n — k)) ·ℓ symbols (over the base field ) which is also referred to as the cut-set bound [4]. For all values of n and k, the MDS vector codes that attain the cut-set bound with the sub-packetization level ℓ = (n − k)⌈n/(n−k)⌉ are known in the literature [23,36]. This paper presents a construction for MDS vector codes which simultaneously ensures both small repair bandwidth and small sub-packetization level. The obtained codes have the smallest possible sub-packetization level ℓ = O(n — k) for an MDS vector code and the repair bandwidth which is at most twice the cut-set bound. The paper then generalizes this code construction so that the repair bandwidth of the obtained codes approach the cut-set bound at the cost of increased sub-packetization level. The constructions presented in this paper give MDS vector codes which are linear over the base field .

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when $g = \lceil \frac{w}{2}\rceil$, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat $\in \mathrm{P}$ as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed $\varepsilon > 0$, the difficulty of finding a satisfying assignment to instances of “$(2+\varepsilon)$-Sat” where the density of satisfied literals in each clause is guaranteed to exceed $\frac{1}{2+\varepsilon}$. We also strengthen the results to prove that, given a (2k+1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k+1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain “weak polymorphisms.” The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the “short code” of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287--1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611--649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on $n$-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; coloring a 4-colorable 4-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; and coloring a 3-colorable 3-uniform hypergraph with $(\log n)^{\Omega(1/\log\log\log n)}$ colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, $(\log n)^{O(1)}$ colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for $O(1)$-colorable hypergraphs, and $(\log\log n)^{O(1)}$ for $O(1)$-colorable, 3-uniform hypergraphs.

The Unique Coverage problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in exactly one element. When each $e \in E$ has cardinality at most $k$, it is also known as 1-in-$k$ Hitting Set and admits a simple $\Omega(\frac{1}{\log k})$-approximation algorithm. For constant $k$, we prove that 1-in-$k$ Hitting Set is NP-hard to approximate within a factor $O(\frac{1}{\log k})$. This improves the result of Guruswami and Zhou [Theory Comput., 8 (2012), pp. 239--267], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor $O(\frac{1}{\log^{1 - \epsilon} n})$ for any $\epsilon > 0$, unless NP admits quasi-polynomial time algorithms. This improves the results of Demaine et al. [SIAM J. Comput., 38 (2008), pp. 1464--1483], including their $\approx 1/\log^{1/3} n$ inapproximability factor, which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for the Set Cover and Constraint Satisfaction Problems, made efficient by various derandomization methods based on bounded independence.

Given an undirected graph $G = (V_G, E_G)$ and a fixed “pattern” graph $H = (V_H, E_H)$ with $k$ vertices, we consider the $H$-Transversal and $H$-Packing problems. The former asks to find the smallest $S \subseteq V_G$ such that the subgraph induced by $V_G \setminus S$ does not have $H$ as a subgraph, and the latter asks to find the maximum number of pairwise disjoint $k$-subsets $S_1, \ldots, S_m \subseteq V_G$ such that the subgraph induced by each $S_i$ has $H$ as a subgraph. We prove that if $H$ is 2-connected, $H$-Transversal and $H$-Packing are almost as hard to approximate as general $k$-Hypergraph Vertex Cover and $k$-Set Packing, so it is NP-hard to approximate them within a factor of $\Omega (k)$ and $\widetilde \Omega (k)$, respectively. We also show that there is a 1-connected $H$ where $H$-Transversal admits an $O(\log k)$-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of $H$-Transversal where $H$ is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem and give a different hardness proof for directed graphs.

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed k ≥ 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/3. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 – ⊝(1/k), since 1 – 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between 1/3 and 1/2 for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.

Communication complexity investigates the amount of communication needed for two or more players to determine some joint function of their private inputs. For many interesting functions, the communication complexity can be much smaller than basic information theoretic measures associated with the players' inputs such as the input length, the entropy, or even the conditional entropy. Communication complexity of many functions reduces further when the players share randomness. Classical works studied the communication complexity of functions when the interacting players share randomness perfectly, i.e., they get identical copies of randomness from a common source. This paper considers the variant of this question when the players share randomness imperfectly, i.e., when they get noisy copies of the randomness produced by some common source. Our main result shows that any function that can be computed by a k-bit protocol in the perfect sharing model has a 2k-bit protocol in the setting of imperfectly shared randomness and such an exponential growth is necessary. Our upper bound relies on ideas from locality sensitive hashing, while lower bounds rely on hypercontractivity and a new invariance principle tailored for communication protocols.

The Reed-Muller (RM) code, encoding n-variate degree-d polynomials over Fqfor dqn, has a relative distance 1 - d/q and can be list decoded from a 1- O(√d/q) fraction of errors. In this paper, for d ≪ q, we give a length-efficient puncturing of such codes, which (almost) retains the distance and list decodability properties of the RM code, but has a much better rate. Specifically, when q = Ω(d2/ε2), we give an explicit rate Ω (ε/d!) puncturing of RM codes, which have a relative distance at least (1 - √ε) and efficient list decoding up to (1 - √ε) error fraction. This almost matches the performance of random puncturings, which work with the weaker field size requirement q = Ω(d/ε2). We can also improve the field size requirement to the optimal (up to constant factors) q = Ω(d/ε), at the expense of a worse list decoding radius of 1-ε1/3and rate Ω (ε/d!). The first of the above tradeoffs is obtained by substituting for the variables functions with carefully chosen pole orders from an algebraic function field; this leads to a puncturing for which the RM code is a subcode of a certain algebraic-geometric code (which is known to be efficiently list decodable). The second tradeoff is obtained by concatenating this construction with a Reed-Solomon-based multiplication friendly pair, and using the list recovery property of algebraic-geometric codes.

The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any ε > 0): 1) codes that can correct a fraction 1 - ε of deletions with rate poly(ε) over an alphabet of size poly(1/ε); 2) binary codes of rate 1-Õ(√ε) that can correct a fraction ε of deletions; and 3) Binary codes that can be list-decoded from a fraction (1/2-ε) of deletions with rate poly(ε). This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The abovementioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors.

A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f are sufficient to determine f. This is also necessary in a strong sense: given k-1 evaluations, we learn nothing about the value of f on any k'th point. In this paper, we study a variant of the polynomial interpolation problem. Instead of querying entire evaluations of f (which are elements of a large field F), we are allowed to query partial evaluations; that is, each evaluation delivers a few elements from a small subfield of F, rather than a single element from F. We show that in this model, one can do significantly better than in the traditional setting, in terms of the amount of information required to determine the missing evaluation. More precisely, we show that only O(k) bits are necessary to recover a missing evaluation. In contrast, the traditional method of looking at k evaluations requires Omega(k log(k)) bits. We also show that our result is optimal for linear methods, even up to the leading constants. Our motivation comes from the use of Reed-Solomon (RS) codes for distributed storage systems, in particular for the exact repair problem. The traditional use of RS codes in this setting is analogous to the traditional interpolation problem. Each node in a system stores an evaluation of f, and if one node fails we can recover it by reading k other nodes. However, each node is free to send less information, leading to the modified problem above. The quickly-developing field of regenerating codes has yielded several codes which take advantage of this freedom. However, these codes are not RS codes, and RS codes are still often used in practice; in 2011, Dimakis et al. asked how well RS codes could perform in this setting. Our results imply that RS codes can also take advantage of this freedom to download partial symbols. In some parameter regimes---those with small levels of sub-packetization---our scheme for RS codes outperforms all known regenerating codes. Even with a high degree of sub-packetization, our methods give non-trivial schemes, and we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.

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.

Suppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar.

We consider the robust curve fitting problem, for both algebraic and Fourier (trigonometric) polynomials, in the presence of outliers. In particular, we study the model of Arora and Khot (STOC 2002), who were motivated by applications in computer vision. In their model, the input data consists of ordered pairs (xi, yi) ε [-1, 1] × [-1, 1], i = 1, 2,..., N, and there is an unknown degree-d polynomial p such that for all but ρ fraction of the i, we have |p(xi) - yi|≤ δ. Unlike Arora-Khot, we also study the trigonometric setting, where the input is from T × [-1, 1], where T is the unit circle. In both scenarios, the i corresponding to errors are chosen randomly, and for such i the errors in the yi can be arbitrary. The goal is to output a degree-d polynomial q such that ||p - q||∞is small (for example, O(δ)). Arora and Khot could achieve a polynomial-time algorithm only for ρ = 0. Daltrophe et al. observed that a simple median-based algorithm can correct errors if the desired accuracy δ is large enough. (Larger δ makes the output guarantee easier to achieve, which seems to typically outweigh the weaker input promise.) We dramatically expand the range of parameters for which recovery of q is possible in polynomial time. Specifically, we show that there are polynomial-time algorithms in both settings that recover q up to l∞ error O(δ.99) provided 1) ρ ≤/c1log d and δ ≥ 1/(log d)c, or 2) ρ ≤ c1/log log d/log2 d and δ ≥ 1/dc. Here c is any constant and c1 is a small enough constant depending on c. The number of points that suffices is N = Õ(d) in the trigonometric setting for random xior arbitrary xithat are roughly equally spaced, or in the algebraic setting when the xiare chosen according to the Chebyshev distribution, and N = Õ(d2) in the algebraic setting with random (or roughly equally spaced) xi.

This work constructs codes that are efficiently decodable from a constant fraction of worst-case insertion and deletion errors in three parameter settings: (i) Binary codes with rate approaching 1; (ii) Codes with constant rate for error fraction approaching 1 over fixed alphabet size; and (iii) Constant rate codes over an alphabet of size k for error fraction approaching (k - 1)/(k + 1). When errors are constrained to deletions alone, efficiently decodable codes in each of these regimes were constructed recently. We complete the picture by constructing similar codes that are efficiently decodable in the insertion/deletion regime.

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.

The Unique Coverage problem, given a universe V of elements and a collection E of subsets of V, asks to find S ⊆ V to maximize the number of e ∊ E that intersects S in exactly one element. When each e ∊ E has cardinality at most k, it is also known as 1-in-k Hitting Set, and admits a simple -approximation algorithm. For constant k, we prove that 1-in-k Hitting Set is NP-hard to approximate within a factor . This improves the result of Guruswami and Zhou [SODA'11, ToC'12], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor for any ∊ > 0, unless NP admits quasipolynomial time algorithms. This improves the results of Demaine et al. [SODA'06, SICOMP'08], including their ≈ 1/log1/3 n inapproximability factor which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence.

We consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process that adds the errors can be described by a sufficiently “simple” circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only in efficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors: We give the first construction of a polynomial-time encodable/decodable code for additive (a.k.a. oblivious ) channels that achieve the Shannon capacity 1 − H ( p ). These are channels that add an arbitrary error vector e ∈ {0, 1} N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the randomness of the encoder or the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List decoding for polynomial-time channels: For every constant c > 0, we construct codes with optimal rate (arbitrarily close to 1 − H ( p )) that efficiently recover a short list containing the correct message with high probability for channels describable by circuits of size at most N c . Our construction is not fully explicit but rather Monte Carlo (we give an algorithm that, with high probability, produces an encoder/decoder pair that works for all time N c channels). We are not aware of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list decoding with an impossibility result showing that, in a large range of parameters ( p > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate.

The Unique Games Conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work, we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem, known as L p Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points X = {α 1 , … , α m } ⊆ R n and a parameter k (possibly depending on n ). The goal is to find a subspace H of R n of dimension k that minimizes the ℓ p norm of the Euclidean distances to the points in X . For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p = ∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p ∈ (2, ∞), and for k = n − 1, it is NP-hard to approximate this problem to within a factor of γ p − ϵ for constant ϵ > 0, where γ p is the p th norm of a standard Gaussian random variable. This matches the γ p approximation algorithm obtained by Deshpande, Tulsiani, and Vishnoi who also showed the same hardness result under the UGC. The second problem we study is the related L p Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor, and Schechtman. Here, the input is a multilinear quadratic form ∑ n i , j = 1 a ij x i x j and the goal is to maximize the quadratic form over the ℓ p unit ball, namely, all x with ∑ n i = 1 | x i | p ⩽ 1. The problem is polynomial time solvable for p = 2. We show that for any constant p ∈ (2, ∞), it is NP-hard to approximate the quadratic form to within a factor of γ 2 p − ϵ for any ϵ > 0. The same hardness factor was shown under the UGC by Kindler et al. We also obtain a γ 2 p -approximation algorithm for the problem using the convex relaxation of the problem defined by Kindler et al. A γ 2 p approximation algorithm has also been independently obtained by Naor and Schechtman. These are the first approximation thresholds, proven under P ≠ NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves do not explicitly involve the Gaussian distribution.

Non-malleable codes, introduced by Dziembowski et al., encode messages s in a manner, so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family P of tampering functions that is not too large (for instance, when I≤I 22αnfor some α2αn, there exist non-malleable codes against P with rate arbitrarily close to 1-α [this is achieved with high probability (w.h.p.) by a randomized construction]. We show the existence of families of size exp(nO(1)2αn) against which there is no non-malleable code of rate 1 - α (in fact this is the case w.h.p for a random family of this size). We also show that 1 - α is the best achievable rate for the family of functions, which are only allowed to tamper the first αn bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword, a model which has received some attention recently) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 and family P of size 2nc, in particular tampering functions with, say, cubic size circuits.

We construct an explicit family of Fh-linear rankmetric codes over any field Fh that enables efficient list-decoding up to a fraction p of errors in the rank metric with a rate of 1 - ρ - e, for any desired ρ ∈ (0, 1) and e > 0. This is the first explicit construction of positive rate rank-metric codes for efficient list-decoding beyond the unique decoding radius. Our codes are explicit subcodes of the well-known Gabidulin codes, which encode linearized polynomials of low degree via their values at a collection of linearly independent points. The subcode is picked by restricting the message polynomials to an Fh-subspace that evades the structured subspaces over an extension field Fht that arise in our linear-algebraic list decoder for Gabidulin codes. This subspace is obtained by combining subspace designs constructed by Guruswami and Kopparty (FOCS'13) with subspace-evasive varieties due to Dvir and Lovett (STOC'12). We establish a similar result for subspace codes, which have received much attention recently in the context of network coding. We also give explicit subcodes of folded Reed-Solomon (RS) codes with small folding order, which are list-decodable (in the Hamming metric) with optimal redundancy, motivated by the fact that listdecoding RS codes reduces to list-decoding such folded RS codes. However, as we only list-decode a subcode of these codes, the Johnson radius continues to be the best known error fraction for list-decoding RS codes.

An emerging theory of "linear algebraic pseudorandomness: aims to understand the linear algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension expanders, seeded rank condensers, two-source rank condensers, and rank-metric codes. In particular, with the recent construction of near-optimal subspace designs by Guruswami and Kopparty as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps F^n to F^t for t<

Given an undirected graph G=(V,E) and a fixed pattern graph H with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest subset S of vertices such that the subgraph induced by V - S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1, ..., Sm such that the subgraph induced by each Si has H as a subgraph. We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Omega(k) and Omega(k / polylog(k)) respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to 1 with some probability achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), where satisfaction of each constraint only depends on the number of true literals in its scope. Thus a SCSP of arity k can be described by a subset of allowed number of true literals. For SCSPs without negation, we conjecture that a simple sufficient condition to be approximation resistant by Austrin and Hastad is indeed necessary. We show that this condition has a compact analytic representation in the case of symmetric CSPs (depending only on the gap between the largest and smallest numbers in S), and provide the rationale behind our conjecture. We prove two interesting special cases of the conjecture, (i) when S is an interval and (ii) when S is even. For SCSPs with negation, we prove that the analogous sufficient condition by Austrin and Mossel is necessary for the same two cases, though we do not pose an analogous conjecture in general.

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ taking values in $\mathbb{Z}_q$, we show \[ H(X_1 + X_2 \mid Y_1, Y_2) - H(X|Y) \ge α(q) \cdot H(X|Y) (1-H(X|Y)) \] for some $α(q) > 0$, where $H(\cdot)$ is the normalized (by factor $\log_2 q$) entropy. Our motivation is an effective analysis of the finite-length behavior of polar codes, and the assumption of $q$ being prime is necessary. For $X$ supported on infinite groups without a finite subgroup and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao (2010). We use our sumset inequality to analyze Arıkan's construction of polar codes and prove that for any $q$-ary source $X$, where $q$ is any fixed prime, and any $ε> 0$, polar codes allow {\em efficient} data compression of $N$ i.i.d. copies of $X$ into $(H(X)+ε)N$ $q$-ary symbols, as soon as $N$ is polynomially large in $1/ε$. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring $q$ into primes and combining different polar codes for each prime in factorization. A consequence of our result for noisy channel coding is that for {\em all} discrete memoryless channels, there are explicit codes enabling reliable communication within $ε> 0$ of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in $1/ε$. The result was previously shown for the special case of binary input channels (Guruswami-Xia '13 and Hassani-Alishahi-Urbanke '13), and this work extends the result to channels over any alphabet.

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when $g = \lceil \frac{w}{2}\rceil$, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat $\in \mathrm{P}$ as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed $\varepsilon > 0$, the difficulty of finding a satisfying assignment to instances of “$(2+\varepsilon)$-Sat” where the density of satisfied literals in each clause is guaranteed to exceed $\frac{1}{2+\varepsilon}$. We also strengthen the results to prove that, given a (2k+1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k+1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain “weak polymorphisms.” The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.

Locally testable codes (LTCs) of constant minimum (absolute) distance that allow the tester to make a nearly linear number of queries have become the focus of attention recently due to their connections to central questions in approximability theory. In particular, the binary Reed-Muller code of block length N and absolute distance d is known to be testable with O(N/d) queries, and has a dimension of  N – (log N)log d. The polylogarithmically small co-dimension is the basis of constructions of small set expanders with many “bad” eigenvalues, and size-efficient PCPs based on a shorter version of the long code. The smallest possible co-dimension for a distance d code (without any testability requirement) is , achieved by BCH codes. This raises the natural question of understanding where in the spectrum between the two classical families, Reed-Muller and BCH, the optimal co-dimension of a distance d LTC lies — in other words the “price” one has to pay for local testability. One promising approach for constructing LTCs is to focus on affine-invariant codes, whose structure makes testing guarantees easier to deduce than for general codes. Along these lines, the authors of [HRZS13] and [GKS13] recently constructed an affine-invariant family of high-rate LTCs with slightly smaller co-dimension than Reed-Muller codes. In this work, we show that their construction is essentially optimal among linear affine-invariant LTCs that contain the Reed-Muller code of the appropriate degree.

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs (k=2), the minimum vertex cover can be computed in polynomial time. For $k \ge 3,$ this problem is known to be NP-hard. For general $k$, the problem was studied by Lovász, who gave a $\frac{k}{2}$-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman, and Krivelevich showed a tight integrality gap of $(\frac{k}{2} - o(1))$ for the LP relaxation. We further investigate the inapproximability of minimum vertex cover on $k$-uniform $k$-partite hypergraphs and present the following results (here $\varepsilon > 0$ is an arbitrarily small constant): NP-hardness of obtaining an approximation factor of $(\frac{k}{4} - \varepsilon)$ for even $k$ and $(\frac{k}{4} - \frac{1}{4k} - \varepsilon)$ for odd $k$, NP-hardness of obtaining a nearly optimal approximation factor of $(\frac{k}{2}-1+\frac{1}{2k}-\varepsilon)$, and an optimal unique games-hardness for approximation within factor $(\frac{k}{2} - \varepsilon)$, showing the optimality of Lovász's algorithm if one assumes the Unique Games conjecture. The first hardness result is based on a reduction from minimum vertex cover in $r$-uniform hypergraphs, for which NP-hardness of approximating within $r - 1 -\varepsilon$ was shown by Dinur, Guruswami, Khot, and Regev. We include it for its simplicity, despite it being subsumed by the second hardness result. The unique games-hardness result is obtained by applying the results of Kumar, Manokaran, Tulsiani, and Vishnoi, with a slight modification, to the LP integrality gap due to Aharoni, Holzman, and Krivelevich. The modification ensures that the reduction preserves the desired structural properties of the hypergraph. The reduction for the nearly optimal NP-hardness result relies on the multilayered PCP of Dinur, Guruswami, Khot, and Regev and uses a gadget based on biased long codes adapted from the LP integrality gap of Aharoni, Holzman, and Krivelevich. Our reduction requires the analysis of several long codes with different biases, for which we prove structural properties of the so-called cross-intersecting collections of set families, variants of which have been studied in extremal set theory.

We construct an explicit family of linear rank-metric codes over any field F that enables efficient list decoding up to a fraction rho of errors in the rank metric with a rate of 1-rho-eps, for any desired rho in (0,1) and eps > 0. Previously, a Monte Carlo construction of such codes was known, but this is in fact the first explicit construction of positive rate rank-metric codes for list decoding beyond the unique decoding radius. Our codes are explicit subcodes of the well-known Gabidulin codes, which encode linearized polynomials of low degree via their values at a collection of linearly independent points. The subcode is picked by restricting the message polynomials to an F-subspace that evades certain structured subspaces over an extension field of F. These structured spaces arise from the linear-algebraic list decoder for Gabidulin codes due to Guruswami and Xing (STOC'13). Our construction is obtained by combining subspace designs constructed by Guruswami and Kopparty (FOCS'13) with subspace-evasive varieties due to Dvir and Lovett (STOC'12). We establish a similar result for subspace codes, which are a collection of subspaces, every pair of which have low-dimensional intersection, and which have received much attention recently in the context of network coding. We also give explicit subcodes of folded Reed-Solomon (RS) codes with small folding order that are list-decodable (in the Hamming metric) with optimal redundancy, motivated by the fact that list decoding RS codes reduces to list decoding such folded RS codes. However, as we only list decode a subcode of these codes, the Johnson radius continues to be the best known error fraction for list decoding RS codes.

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding n-variate degree-d polynomials over Fqwith q ≳ d/δ, we present an explicit (multi)-set S ⊆ Fqnof size N=poly(nd/δ) such that every nonzero polynomial vanishes on at most delta N points in S. Equivalently, we give an explicit hitting set generator (HSG) for degree-d polynomials of seed length log N = O(d log n + log (1/δ)) with "density" 1-δ (meaning every nonzero polynomial is nonzero with probability at least 1-δ on the output of the HSG). The seed length is optimal up to constant factors, as is the required field size Omega(d/delta). Plugging our HSG into a construction of Bogdanov (STOC'05) gives explicit pseudorandom generators for n-variate degree-d polynomials with error eps and seed length O(d4log n + log (1/ε)) whenever the field size satisfies q gtrsim d6/ε2. Our approach involves concatenating previously known HSGs over large fields with multiplication friendly codes based on algebraic curves. This allows us to bring down the field size to the optimal bounds. Such multiplication friendly codes, which were first introduced to study the bilinear complexity of multiplication in extension fields, have since found other applications, and in this work we give a further use of this notion in algebraic pseudorandomness.

We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2] - 1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT ∈ P as easiness of SAT when 1-in-2 literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when 1-in-3 literals are true, our resultshows, for any fixed ε > 0, the hardness of finding a satisfyingassignment to instances of "(2 + ε)-SAT" where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages s in a manner so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family F of tampering functions that is not too large (for instance, when lF| ≤ 22αn for some α < 1 where n is the number of bits in a codeword).

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints and hard constraints, and the goal is to maximize the weight of satisfied soft constraints while satisfying all the hard constraints. These two extensions contain many fundamental problems not captured by CSPs, and challenge traditional theories about CSPs in a more general framework.

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank 1, and designed to have an automorphism of large order that is used to “fold” the AG code. This generalizes earlier work by the first author on folded AG codes based on cyclotomic function fields. The recent linear-algebraic approach to list decoding can be applied to our new codes, and crucially, we use the Chebotarev density theorem to establish a polynomial upper bound on the list-size for list decoding up to an error fraction approaching 1 – R where R is the rate. The list decoding can be performed in polynomial time given polynomial amount of pre-processed information about the function field. Our construction yields algebraic codes over constant-sized alphabets that can be list decoded up to the Singleton bound — specifically, for any desired rate R ∊ (0, 1) and constant ∊ > 0, we get codes over an alphabet size that can be list decoded up to error fraction 1 – R – ∊ confining close-by messages to a subspace with elements. Previous results for list decoding up to error-fraction 1 – R – ∊ over constant-sized alphabets were either based on concatenation or involved taking a carefully chosen subcode of algebraic-geometric codes. In contrast, our result shows that these folded algebraic-geometric codes themselves have the claimed list decoding property. Further, our methods to get function fields with the properties needed for constructing and decoding the code might be of independent algebraic interest.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

We study certain combinatorial aspects of listdecoding, motivated by the exponential gap between the known upper bound (of O(1/γ)) and lower bound (of Ωp(log(1/γ))) for the list size needed to list decode up to error fraction p with rate γ away from capacity, i.e., 1 - h(p) - γ [here p E (0, 1/2) and γ > 0]. Our main result is that we prove that in any binary code C ⊆ (0, 1)nof rate 1 - h(p) - γ, there must exist a set l ⊂ C of p(1/√γ) codewords such that the average distance of the points in L from their centroid is at most pn. In other words, there must exist Ωp(1/√γ) codewords with low average radius. The standard notion of list decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned Ωp(log(1/γ)) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one cannot improve the Ωp(log(1/γ)) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constantweight codes [this is a typical approach for negative results in coding theory, including the Ωp(log(1/γ)) list-size lower bound]. On a positive note, our Ωp(1/√γ) lower bound for average radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap γ of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from p) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of Ωp(1/γ) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are Ωp(1/γ) for errors and expΩp(log(1/γ)) for erasures.

We prove n^(1+Omega(1/p))/p^O(1) lower bounds for the space complexity of p-pass streaming algorithms solving the following problems on n-vertex graphs: * testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size), * testing if two specific vertices are at distance at most 2(p+1) in an undirected graph, * testing if there is a directed path from s to t for two specific vertices s and t in a directed graph. Prior to our result, it was known that these problems require Omega(n^2) space in one pass, but no n^(1+Omega(1)) lower bound was known for any p>=2. These streaming results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices reachable from a specific vertex in exactly p+1 steps intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem.

We develop new techniques to incorporate the recently proposed “short code” (a low-degree version of the long code) into the construction and analysis of PCPs in the classical “Label Cover + Fourier Analysis” framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs and certain coloringtype problems. In particular, we show a hardness for a variant of hypergraph coloring (with hyperedges of size 6), with a gap between 2 and exp(2Ω(√log log N)) number of colors where N is the number of vertices. This is the first hardness result to go beyond the O(log N) barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known O(log log N)-coloring hardness for 2-colorable hypergraphs, and an exponential improvement over the (logN)Ω(1)-coloring hardness for O(1)-colorable hypergraphs. Stated in terms of “covering complexity,” we show that for 6-ary Boolean CSPs, it is hard to decide if a given instance is perfectly satisfiable or if it requires more than 2Ω(√log log N) assignments for covering all of the constraints. While our methods do not yield a result for conventional hypergraph coloring due to some technical reasons, we also prove hardness of (log N)Ω(1)-coloring 2-colorable 6-uniform hypergraphs (this result relies just on the long code). A key algebraic result driving our analysis concerns a very low-soundness error testing method for Reed-Muller codes. We prove that if a function β : F2m→ F2is 2Ω(d)far in absolute distance from polynomials of degree m-d, then the probability that deg(βg) ≤ m-3d/4 for a random degree d/4 polynomial g is doubly exponentially small in d.

A subspace design is a collection {H1, H2, . . . , HM} of subspaces of Fmqwith the property that no low-dimensional subspace W of Fqmintersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters. Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial PWthat has several roots for each H that non-trivially intersects W. The construction of PWis based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.

We prove that, for all binary-input symmetric memory less channels, polar codes enable reliable communication at rates within ε > 0 of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a polynomial in 1/ε. Polar coding gives the first known explicit construction with rigorous proofs of all these properties. We give an elementary proof of the capacity achieving property of polar codes that does not rely on the martingale convergence theorem. As a result, we are able to explicitly show that polar codes can have block length (and consequently also encoding and decoding complexity) that is bounded by a polynomial in the gap to capacity. The generator matrix of such polar codes can be constructed in polynomial time using merging of channel output symbols to reduce the alphabet size of the channels seen at the decoder.

Shannon's monumental 1948 work laid the foundations for the rich fields of information and coding theory. The quest for efficient coding schemes to approach Shannon capacity has occupied researchers ever since, with spectacular progress enabling the widespread use of error-correcting codes in practice. Yet the theoretical problem of approaching capacity arbitrarily closely with polynomial complexity remained open except in the special case of erasure channels. In 2008, Arikan proposed an insightful new method for constructing capacity-achieving codes based on channel polarization. In this talk, I will begin with a self-contained survey of Arikan's celebrated construction of polar codes, and then discuss our recent proof (with Patrick Xia) that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within epsilon > 0 of the Shannon capacity with block length (delay), construction complexity, and decoding complexity all bounded by a polynomial in the gap to capacity, i.e., by poly(1/epsilon). Polar coding gives the first explicit construction with rigorous proofs of all these properties; previous constructions were not known to achieve capacity with less than exp(1/epsilon) decoding complexity. We establish the capacity-achieving property of polar codes via a direct analysis of the underlying martingale of conditional entropies, without relying on the martingale convergence theorem. This step gives rough polarization (noise levels epsilon for the good channels), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters. Our effective bounds imply that polar codes can have block length bounded by poly(1/epsilon). We also show that the generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process.

We prove that a random linear code over $\mathbb{F}_q$, with probability arbitrarily close to 1, is list decodable at radius $1-1/q-\epsilon$ with list size $L=O(1/\epsilon^2)$ and rate $R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in $1/\epsilon$ and constant factors depending on $q$, this matches the lower bound $L=\Omega_q(1/\epsilon^2)$ for the list size and upper bound $R=O_q(\epsilon^2)$ for the rate. Previously only existence (and not abundance) of such codes was known for the special case $q=2$ (Guruswami et al., 2002). In order to obtain our result, we employ a relaxed version of the well-known Johnson bound on list decoding that translates the average Hamming distance between codewords to list decoding guarantees. We furthermore prove that the desired average-distance guarantees hold for a code provided that a natural complex matrix encoding the codewords satisfies the restricted isometry property with respect to the Euclidean norm. For the case of random binary linear codes, this matrix coincides with a random submatrix of the Hadamard--Walsh transform matrix that is well studied in the compressed sensing literature. Finally, we improve the analysis of Rudelson and Vershynin (2008) on the number of random frequency samples required for exact reconstruction of $k$-sparse signals of length $N$. Specifically, we improve the number of samples from $O(k \log(N) \log^2(k) (\log k + \log\log N))$ to $O(k \log(N) \cdot \log^3(k))$. The proof involves bounding the expected supremum of a related Gaussian process by using an improved analysis of the metric defined by the process. This improvement is crucial for our application in list decoding.

We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any ε, δ ∊ (0, 1), given cost and demand graphs with edge weights respectively, we can find a set T ⊆ V with at most times the optimal non-uniform sparsest cut value, in time 2r/(δε) poly(n) provided Λr ≥ Φ*/(1 − δ). Here Λr is the r'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; C(T, V \ T) (resp. D(T, V \ T)) is the weight of edges crossing the (T, V \ T) cut in cost (resp. demand) graph and Φ* is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the r'th smallest eigenvalue of the normalized Laplacian playing the role of Λr(G) in the latter two cases. Our proof is based on an ℓ1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting ℓ1-embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [9] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code dimension. By pre-coding the message polynomials into a subspace-evasive set, we get a Monte Carlo construction of a subcode of Reed-Solomon codes that can be list decoded from a fraction (1-R-ε) of errors in polynomial time (for any fixed ε > 0) with a list size of O(1/ε). Our methods extend to algebraic-geometric (AG) codes, leading to a similar claim over constant-sized alphabets. This matches parameters of recent results based on folded variants of RS and AG codes. but our construction here gives subcodes of Reed-Solomon and AG codes themselves (albeit with restrictions on the evaluation points).

How can web services that depend on user generated content discern fraudulent input by spammers from legitimate input? In this paper we focus on the social network Facebook and the problem of discerning ill-gotten Page Likes, made by spammers hoping to turn a profit, from legitimate Page Likes. Our method, which we refer to as CopyCatch, detects lockstep Page Like patterns on Facebook by analyzing only the social graph between users and Pages and the times at which the edges in the graph (the Likes) were created. We offer the following contributions: (1) We give a novel problem formulation, with a simple concrete definition of suspicious behavior in terms of graph structure and edge constraints. (2) We offer two algorithms to find such suspicious lockstep behavior - one provably-convergent iterative algorithm and one approximate, scalable MapReduce implementation. (3) We show that our method severely limits "greedy attacks" and analyze the bounds from the application of the Zarankiewicz problem to our setting. Finally, we demonstrate and discuss the effectiveness of CopyCatch at Facebook and on synthetic data, as well as potential extensions to anomaly detection problems in other domains. CopyCatch is actively in use at Facebook, searching for attacks on Facebook's social graph of over a billion users, many millions of Pages, and billions of Page Likes.

Folded Reed-Solomon (RS) codes are an explicit family of codes that achieve the optimal tradeoff between rate and list error-correction capability: specifically, for any ε > 0, Guruswami and Rudra presented annO(1/ ε)time algorithm to list decode appropriate folded RS codes of rateRfrom a fraction 1-R-ε of errors. The algorithm is based on multivariate polynomial interpolation and root-finding over extension fields. It was noted by Vadhan that interpolating a linear polynomial suffices for a statement of the above form. Here, we give a simple linear-algebra-based analysis of this variant that eliminates the need for the computationally expensive root-finding step over extension fields (and indeed any mention of extension fields). The entire list-decoding algorithm is linear-algebraic, solving one linear system for the interpolation step, and another linear system to find a small subspace of candidate solutions. Except for the step of pruning this subspace, the algorithm can be implemented to run in quadratic time. We also consider a closely related family of codes, called (orderm) derivative codes and defined over fields of large characteristic, which consist of the evaluations offas well as its firstm-1 formal derivatives atNdistinct field elements. We show how our linear-algebraic methods for folded RS codes can be used to show that derivative codes can also achieve the above optimal tradeoff. The theoretical drawback of our analysis for folded RS codes and derivative codes is that both the decoding complexity and proven worst-case list-size bound arenΩ(1/ ε). By combining the above idea with a pseudorandom subset of all polynomials as messages, we get a Monte Carlo construction achieving a list-size bound ofO(1/ ε2) which is quite close to the existentialO(1/ ε) bound (however, the decoding complexity remainsnΩ(1/ ε)). Our work highlights that constructing an explicit subspace-evasive subset that has small intersection with low-dimensional subspaces-an interesting problem in pseudorandomness in its own right-could lead to explicit codes with better list-decoding guarantees.

Convex relaxations based on different hierarchies of linear/semi-definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of rounds r in the hierarchy, though the complexity of solving (or even writing down the solution for) the r'th level program grows as nΩ(r)where n is the input size. In this work, we observe that many of these algorithms are based on local rounding procedures that only use a small part of the SDP solution (of size nO(1)2O(r)instead of nΩ(r)). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to nO(1)2O(r)time algorithms to obtain the same guarantees in many cases as the earlier nO(r)time algorithms based on r rounds of the Lasserre hierarchy. In particular, guarantees based on O(log n) rounds can be realized in polynomial time. For instance, one can (i) get O(1/λr) approximations for graph partitioning problems such as minimum bisection and small set expansion in nO(1)2O(r)time, where λris the r'th smallest eigenvalue of the graph's normalized Laplacian; (ii) a similar guarantee in nO(1)kO(r)for Unique Games where k is the number of labels (the polynomial dependence on k is new); and (iii) find an independent set of size Ω(n) in 3-colorable graphs in (n2r)O(1)time provided λn-r<; 17/16. We develop and describe our algorithm in a fairly general abstract framework. The main technical tool in our work, which might be of independent interest in convex optimization, is an efficient ellipsoid algorithm based separation oracle for convex programs that can output a certificate of infeasibility with restricted support. This is used in a recursive manner to find a sequence of consistent points in nested convex bodies that “fools” local rounding algorithms.

We present a construction of subspace codes along with an efficient algorithm for list decoding from both insertions and deletions, handling an information-theoretically maximum fraction of these with polynomially small rate. Our construction is based on a variant of the folded Reed-Solomon codes in the world of linearized polynomials, and the algorithm is inspired by the recent linear-algebraic approach to list decoding [4]. Ours is the first list decoding algorithm for subspace codes that can handle deletions; even one deletion can totally distort the structure of the basis of a subspace and is thus challenging to handle. When there are only insertions, we also present results for list decoding subspace codes that are the linearized analog of Reed-Solomon codes (proposed in [15, 8], and closely related to the Gabidulin codes for rank-metric coding), obtaining some improvements over similar results in [10].

The Densest k-subgraph problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for Densest k-subgraph: the current best algorithm gives an ≈ O(n1/4) approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P ≠ NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of Densest k-subgraph and its variants. Thus, understanding the approximability of Densest k-subgraph is an important challenge. In this work, we give evidence for the hardness of approximating Densest k-subgraph within polynomial factors. Specifically we expose the limitations of strong semidefinite programs from SDP hierarchies in solving Densest k-subgraph. Our results include: A lower bound of Ω(n1/4/log3 n) on the integrality gap for Ω(log n / log log n) rounds of the Sherali-Adams relaxation for Densest k-subgraph. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdös-Renyi random graphs. For every ∊ > 0, a lower bound of n2/53 − ∊ on the integrality gap of nΩ(∊) rounds of the Lasserre SDP relaxation for Densest k-subgraph, and an nΩ∊(1) gap for n1−∊ rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for Densest k-subgraph, our results show that beating a factor of nΩ(1) is a barrier for even the most powerful SDPs, and in fact even beating the best known n1/4 factor is a barrier for current techniques. Our results indicate that approximating Densest k-subgraph within a polynomial factor might be a harder problem than Unique Games or Small Set Expansion, since these problems were recently shown to be solvable using n∊ω(1) rounds of the Lasserre hierarchy where ∊ is the completeness parameter in Unique Games and Small Set Expansion.

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem, known as the Lp Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points S = {a1, …, am} ⊆ ℝn and a parameter k (possibly depending on n). The goal is to find a subspace H of ℝn of dimension k that minimizes the ℓp norm of the Euclidean distances to the points in S. For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p = ∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p (2 < p < ∞), and for k = n − 1, it is NP-hard to approximate this problem to within a factor of γp − ∊ for constant ∊ > 0, where γp is the pth norm of a standard Gaussian random variable. This matches the γp approximation algorithm obtained by Deshpande, Tulsiani and Vishnoi [9] who also showed the same hardness result under the Unique Games Conjecture. The second problem we study is the related Lp Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman [24]. Here, the input is a multilinear quadratic form σni,j=1 aijxixj and the goal is to maximize the quadratic form over the ℓp unit ball, namely all x with σni=1 |xi|p = 1. The problem is polynomial time solvable for p = 2. We show that for any constant p (2 < p < ∞), it is NP-hard to approximate the quadratic form to within a factor of γ2p − ∊ for any ∊ > 0. The same hardness factor was shown under the UGC in [24]. We also obtain a γ2p-approximation algorithm for the problem using the convex relaxation of the problem defined by [24]. A γ2p approximation algorithm has also been independently obtained by Naor and Schechtman [27]. These are the first approximation thresholds, proven under P ≠ NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves have no mention of Gaussians.

We prove that for any real-valued matrix X ∊ ℝm×n, and positive integers r ≥ k, there is a subset of r columns of X such that projecting X onto their span gives a -approximation to best rank-k approximation of X in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in O(rnmω log m) arithmetic operations where ω is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in O(rnm2) arithmetic operations.

We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε --- it can be made exp(~O(1/ε2)) which is not much worse than the non-constructive exp(1/ε) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time Oε(Nc) for an absolute constant $c$, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of function fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N.

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and error-correction capability: specifically, for any ε >; 0, the author and Rudra (2006, 08) presented an nO(1/ε)time algorithm to list decode appropriate folded RS codes of rate R from a fraction 1-R-ε of errors. The algorithm is based on multivariate polynomial interpolation and root-finding over extension fields. It was noted by Vadhan that interpolating a linear polynomial suffices if one settles for a smaller decoding radius (but still enough for a statement of the above form). Here we give a simple linear-algebra based analysis of this variant that eliminates the need for the computationally expensive rootfinding step over extension fields (and indeed any mention of extension fields). The entire list decoding algorithm is linearalgebraic, solving one linear system for the interpolation step, and another linear system to find a small subspace of candidate solutions. Except for the step of pruning this subspace, the algorithm can be implemented to run in quadratic time. The theoretical drawback of folded RS codes are that both the decoding complexity and proven worst-case list-size bound are nΩ(1/ε). By combining the above idea with a pseudorandom subset of all polynomials as messages, we get a Monte Carlo construction achieving a list size bound of O(1/ε2) which is quite close to the existential O(1/ε) bound (however, the decoding complexity remains nΩ(1/ε)). Our work highlights that constructing an explicit subspaceevasive subset that has small intersection with low-dimensional subspaces - an interesting problem in pseudorandomness in its own right - could lead to explicit codes with better listdecoding guarantees.

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global lin- ear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time nO(r/ε2)with approximation ratio (1+ε)/min{1,λr}, where λris the r'th smallest eigenvalue of the normalized graph Laplacian L. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply (1 + O(ε)) factor approximation in time nO(r*/ε2)where r* is the number of eigenvalues of L smaller than 1 - ε. This perhaps gives some indication as to why even showing mere APX-hardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure). For Unique Games, we give a factor (1 + (2+ε)/λr) approximation for minimizing the number of unsatisfied constraints in nO(r/ε)time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than 1 + o(1).

We prove almost tight hardness results under randomized reductions for finding independent sets in bounded degree graphs and hypergraphs that admit a good coloring. Our specific results include the following (where Δ, a constant, is a bound on the degree, and n is the number of vertices): NP-hardness of finding an independent set of size larger than in a 2-colorable r-uniform hypergraph for each fixed r ≥ 4. A simple algorithm is known to find independent sets of size in any r-uniform hypergraph of maximum degree Δ. Under a combinatorial conjecture on hypergraphs, the (log Δ)1/(r–1) factor in our result is necessary. Conditional hardness of finding an independent set with more than vertices in a k-colorable (with k ≥ 7) graph for some absolute constant c ≤ 4, under Khot's 2-to-1 Conjecture. This suggests the near-optimality of Karger, Motwani and Sudan's graph coloring algorithm which finds an independent set of size in k-colorable graphs. Conditional hardness of finding independent sets of size in almost 2-colorable 3-uniform hypergraphs, under Khot's Unique Games Conjecture. This suggests the optimality of the known algorithms to find an independent set of size in 2-colorable 3-uniform hypergraphs. Conditional hardness of finding an independent set of size more than in r-uniform hypergraphs that contain an independent set of size n(1 − O (log r/r)) assuming the Unique Games Conjecture.

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a near-satisfiable instance. 1. Given an instance of Max Horn-3SAT that admits an assignment satisfying (1 –ε) of its constraints for some small constant ε > 0, it is hard to find an assignment satisfying more than (1 − 1/O(log(1/ε))) of the constraints. This matches a linear programming based algorithm due to Zwick [Zwi98], resolving the natural open question raised in that work concerning the optimality of the approximation bound. Given a (1 − ε) satisfiable instance of Max Horn-2SAT for some constant ε > 0, it is possible to find a (1 − 2ε)-satisfying assignment efficiently. This improves the algorithm given in [KSTW00] which finds a (1 − 3ε)-satisfying assignment, and also matches the (1 − cε) hardness for any c < 2 derived from vertex cover (under UGC). 2. An instance of Max 1-in-k-HS consists of a universe U and a collection C of subsets of U of size at most k, and the goal is to find a subset of U that intersects the maximum number of sets in C at a unique element. We prove that Max 1-in-k-HS is hard to approximate within a factor of O(1/log k) for every fixed integer k. This matches (up to constant factors) an easy factor Ω(1/log k) approximation algorithm for the problem, and resolves a question posed in [GT05]. It is crucial for the above hardness that sets of size up to k are allowed; indeed, when all sets have size k, there is a simple factor 1/e-approximation algorithm. Our hardness results are proved by constructing integrality gap instances for a semidefinite programming relaxation for the problems, and using Raghavendra's result [Rag08] to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to previous gap constructions where the instances had a good SDP solution by design and the main task was bounding the integral optimum, the challenge in our case is the construction of appropriate SDP vectors and the integral optimum is easy to bound. Our algorithmic results are based on rounding appropriate linear programming relaxations.

In keeping with an annual tradition, this issue of the SIAM Journal on Computing contains extended versions of selected papers from the Fortieth Annual ACM Conference on Theory of Computing (STOC 2008), held in Victoria, British Columbia, May 17–20, 2008. The committee, comprising James Aspnes, Shai Ben-David, Shuchi Chawla, Bernard Chazelle, Steve Chien, Xiaotie Deng, Cynthia Dwork (chair), Martin Dyer, Ronald Fagin, Joan Feigenbaum, Anupam Gupta, Venkatesan Guruswami, Konstantin Makarychev, Elchanan Mossel, Rafael Pass, Oded Regev, Omer Reingold, Ronitt Rubinfeld, David Shmoys, Luca Trevisan, and Andrew Chi-Chih Yao, selected 80 papers from 320 submissions under consideration. Nine of these papers appear in this special section, each one expanded and then refereed according to the journal's exacting standards. The papers cover a diverse set of topics: We thank the authors, the referees, and the full program committee for all the work that lead to this volume.

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for every code, the ratio of its list decoding radius (LDR) to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. We show that for every code, its LDR remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur et al. [in Proceedings of the 40th ACM Symposium on Theory of Computing (STOC '08), 2008, pp. 275–284], who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). Using the notion of generalized Hamming weights, we give better list size bounds for both the tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to one of bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank reduction together with other ideas, we obtain list size bounds that are tight over small fields. Our results give better bounds on the LDR than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson radius.

We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) where each constraint has constant arity is approximation resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining a $\rho'$ approximation for any $\rho'>\rho$ is UG-hard. For the simplest OCSP, the Maximum Acyclic Subgraph (MAS) problem, this implies that obtaining a $\rho$-approximation for any constant $\rho>1/2$ is UG-hard. Specifically, for every constant $\varepsilon>0$ the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction $(1-\varepsilon)$ of its edges, it is UG-hard to find one with more than $(1/2+\varepsilon)$ of its edges. Note that it is trivial to find an acyclic subgraph with $1/2$ the edges by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied, and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset $\Pi\subseteq S_k$ of permutations on $\{1,2,\dots,k\}$. An instance of such an OCSP is a set V and a collection of constraints, each of which is an ordered k-tuple of V. The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in $\Pi$. A random ordering of V is expected to satisfy a $\rho=\frac{|\Pi|}{k!}$ fraction. We show that, for any fixed k, it is hard to obtain a $\rho'$-approximation for $\Pi$-OCSP for any $\rho'>\rho$. The result is in fact stronger: we show that for every $\Lambda\subseteq\Pi\subseteq S_k$, and an arbitrarily small $\varepsilon$, it is hard to distinguish instances where a $(1-\varepsilon)$ fraction of the constraints can be ordered according to $\Lambda$ from instances where at most a $(\rho+\varepsilon)$ fraction can be ordered as in $\Pi$. A special case of our result is that the Betweenness problem is hard to approximate beyond a factor $1/3$. The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation.

The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field Fq,p∈ (0,1 - 1/q) and ε >; 0, it is proved that with high probability a random linear codeCin Fqnof rate (1-Hq(p)-ε) can be list decoded from a fractionpof errors with lists of size at mostO(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the information-theoretically optimal rate of 1 - Hq(p). The best previously known list-size bound was qO(1/ε)(except in the q = 2 case where a list-size bound of O(1/ε) was known). The main technical ingredient in the proof is a strong upper bound on the probability that I random vectors chosen from a Hamming ball centered at the origin have too many (more than Ω(ℓ)) vectors from their linear span also belong to the ball.

Explicit constructions of binary linear codes that are efficiently list-decodable up to a fraction (1/2 - ε) of errors are given. The codes encode k bits into n = poly(k/ε) bits and are constructible and list-decodable in time polynomial in k and 1/ε (in particular, ε need not be constant and can even be polynomially small in n). These results give the best known polynomial dependence of n on k and 1/ε for such codes. Specifically, they are able to achieve n ≤ Õ(k3/ε3+γ) or, if a linear dependence on k is required, n ≤ O(k/ε5+γ) , where γ >; 0 is an arbitrary constant. The best previously known constructive bounds in this setting were n ≤ O(k2/ε4) and n ≤ O(k/ε6) . Nonconstructively, a random linear encoding of length n = O(k/ε2) suffices, but no subexponential algorithm is known for list decoding random codes. In addition to being a basic question in coding theory, codes that are list-decodable from a fraction (1/2 - ε) of errors for ε → 0 are important in several complexity theory applications. For example, the construction with near-cubic dependence on ε yields better hardness results for the problem of approximating NP witnesses. Further, the codes constructed have the property that all nonzero codewords have relative Hamming weights in the range (1/2 - ε, 1/2 + ε); this ε-biased property is a fundamental notion in pseudorandomness.

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently "simple" circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For three classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works for every channel in the class. Unique decoding for additive errors: We give the first construction of a poly-time encodable/decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1-H(p). List-decoding for online log-space channels: A space-S(N) bounded channel reads and modifies the transmitted codeword as a stream, using at most S(N) bits of workspace on transmissions of N bits. For constant S, this captures many models from the literature, including "discrete channels with finite memory" and "arbitrarily varying channels". We give an efficient code with optimal rate (arbitrarily close to 1-H(p)) that recovers a short list containing the correct message with high probability for channels which read and modify the transmitted codeword as a stream, using at most O(\log N) bits of workspace on transmissions of N bits. List-decoding for poly-time channels: For any constant c we give a similar list-decoding result for channels describable by circuits of size at most Nc, assuming the existence of pseudorandom generators.

We show that the list-decodability of random linear codes is as good as that of general random codes. Specifically, for every fixed finite field Fq, p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in Fqn of rate (1-H_q(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the "list decoding capacity" 1-Hq(p). The best previously known list-size bound was qO(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known).

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of LTCs are linear codes and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately, until now it has not even been known whether LTCs need to be nontrivially redundant, i.e., need to have one linear dependency among the low-weight codewords in their dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, nonredundant (in fact, low redundancy) local testing is impossible. Our main theorem is a special case of a more general theorem that applies to any tester for an arbitrary linear LTC $\mathcal{C}$. The general theorem can be used, for instance, to provide an arguably simpler proof of the main result of Ben-Sasson, Harsha, and Raskhodnikova [SIAM J. Comput., 35 (2005), pp. 1–21], which says that testing random low density parity check (LDPC) codes requires linear query complexity. Informally, our more general theorem says the following. Take any basis B for the dual code of $\mathcal{C}$ that is composed of words of small support; i.e., every element of B has very few nonzero entries. Then the dual code of $\mathcal{C}$ must contain many words that (i) are not in B, (ii) have small support, and, most importantly, (iii) are a linear combination of a constant fraction of B.

It is proven that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve, with high probability, the optimal tradeoff between rate and list-decoding radius. In particular, for any 00, there exist concatenated codes of rate at least 1-H(ρ)-ε that are (combinatorially) list-decodable up to a fraction of errors. (The Hamming bound states that the best possible rate for such codes cannot exceed 1-H(ρ), and standard random coding arguments show that this bound is approached by random codes with high probability.) A similar result, with better list size guarantees, holds when the outer code is also randomly chosen. The methods and results extend to the case when the alphabet size is any fixed prime power q ≥ 2.

Aq-ary error-correcting codeC⊆ {1,2,...,q}nis said to be list decodable to radius ρ with list sizeLif every Hamming ball of radius ρ contains at mostLcodewords ofC. We prove that in order for aq-ary code to be list-decodable up to radius (1-1/q)(1- ε)n, we must haveL= Ω(1/ ε2) . Specifically, we prove that there exists a constantcq> 0 and a functionfqsuch that for small enough ε > 0, ifCis list-decodable to radius (1-1/q)(1- ε)nwith list sizecq/ ε2, thenChas at mostfq( ε) codewords, independent ofn. This result is asymptotically tight (treatingqas a constant), since such codes with an exponential (inn) number of codewords are known for list sizeL=O(1/ ε2). A result similar to ours is implicit in Blinovsky ( Problems of Information Transmission, 1986) for the binary (q=2) case. Our proof is simpler and works for all alphabet sizes, and provides more intuition for why the lower bound arises.

Locally testable codes (LTCs) are error- correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately till now it was not even known if LTCs need to be non-trivially redundant, i.e., need to have one linear dependency among the low-weight codewords in its dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, non-redundant (in fact, low redundancy) local testing is impossible.

A permutation constraint satisfaction problem (permCSP) of arity k is specified by a subset LambdasubeSkof permutations on {1,2,...,k}. An instance of such a permCSP consists of a set of variables V and a collection of constraints each of which is an ordered k-tuple of V. The objective is to find a global ordering sigma of the variables that maximizes the number of constraint tuples whose ordering (under sigma) follows a permutation in Lambda. This is just the natural extension of constraint satisfaction problems over finite domains (such as Boolean CSPs) to the world of ordering problems. The simplest permCSP corresponds to the case when Lambda consists of the identity permutation on two variables. This is just the maximum acyclic subgraph (MAS) problem. It was recently shown that the MAS problem is unique-games hard to approximate within a factor better than the trivial 1/2 achieved by a random ordering. Building on this work, in this paper we show that for *every* permCSP of arity 3, beating the random ordering is unique-games hard. The result is in fact stronger: we show that for every LambdasubePisube S3, given an instance of permCSP(Lambda) that is almost-satisfiable, it is hard to find an ordering that satisfies more than Pi/6 +epsiv of the constraints even under the relaxed constraint Pi (for arbitrary epsiv> 0). A special case of our result is that the *Betweenness* problem is hard to approximate beyond a factor 1/3. Interestingly, for *satisfiable* instances of Betweenness, a factor 1/2 approximation algorithm is known. Thus, every permutation CSP of arity up to 3 resists approximation beyond the trivial random ordering threshold. In contrast, for Boolean CSPs, there are both approximation resistant and non-trivially approximable CSPs of arity 3.

We prove the following strong hardness result for learning: Given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with (1-¿)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 + ¿)-fraction of the examples, for arbitrary constant ¿ > 0. In learning theory terms, weak agnostic learning of monomials by halfspaces is NP-hard. This hardness result bridges between and subsumes two previous results which showed similar hardness results for the proper learning of monomials and halfspaces. As immediate corollaries of our result, we give the first optimal hardness results for weak agnostic learning of decision lists and majorities. Our techniques are quite different from previous hardness proofs for learning. We use an invariance principle and sparse approximation of halfspaces from recent work on fooling halfspaces to give a new natural list decoding of a halfspace in the context of dictatorship tests/label cover reductions. In addition, unlike previous invariance principle based proofs which are only known to give Unique Games hardness, we give a reduction from a smooth version of Label Cover that is known to be NP-hard.

We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player i has a nonnegative valuation pi j for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an Õ ( √ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2. The current algorithmic results for MaxMin Allocation are based

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. (1) We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. (2) We show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur.et.al, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). (3)Using the notion of generalized Hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain tight list size bounds for small fields.

Algebraic codes that achieve list decoding capacity were recently constructed by a careful "folding" of the Reed-Solomon code. The "low-degree" nature of this folding operation was crucial to the list decoding algorithm. We show how such folding schemes arise out of the Artin-Frobenius automorphism at primes in Galois extensions. Using this approach, we construct new folded algebraic-geometric codes for list decoding based on cyclotomic function fields with a cyclic Galois group. Such function fields are obtained by adjoining torsion points of the Carlitz action of an irreducible M ∈ Fq[T]. The Reed-Solomon case corresponds to the simplest such extension (corresponding to the case M=T). In the general case, we need to descend to the fixed field of a suitable Galois subgroup in order to ensure the existence of many degree one places that can be used for encoding.

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005]. Our expanders can be interpreted as near-optimal “randomness condensers,” that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)).

Learning an unknown halfspace (also called a perceptron) from labeled examples is one of the classic problems in machine learning. In the noise-free case, when a halfspace consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction $(1-\varepsilon)$ of the examples exists (for some small constant $\varepsilon>0$), it was not known how to efficiently find a halfspace that is correct on even 51% of the examples. Nor was a hardness result that ruled out getting agreement on more than 99.9% of the examples known. In this work, we close this gap in our understanding and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary $\epsilon,\delta > 0$, we prove that given a set of examples-label pairs from the hypercube, a fraction $(1-\varepsilon)$ of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction $(1/2+\delta)$ of the examples. The hardness result is tight since it is trivial to get agreement on $1/2$ the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by Blum et al., in their work on learning halfspaces in the presence of random classification noise [Algorithmica, 22 (1998), pp. 35–52], and raised by authors of some more recent works as well. Along the way, we also obtain a strong hardness result for another basic computational problem: solving a linear system over the rationals.

A polynomial time construction of binary codes with the currently best known tradeoff between rate and error-correction radius is given. Specifically, linear codes over fixed alphabets are constructed that can be list decoded in polynomial time up to the so-called Blokh-Zyablov bound. The work builds upon earlier work by the authors where codes list decodable up to the Zyablov bound (the standard product bound on distance of concatenated codes) were constructed. The new codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. A probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. A ldquolevel-by-levelrdquo decoding algorithm, which crucially uses the list recovery algorithm for the outer folded Reed-Solomon codes, enables list decoding up to the designed distance bound, aka the Blokh-Zyablov bound, for multilevel concatenated codes.

We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant mu Gt 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 - (log n)-mu fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm can decide L' correctly on a 3/4 + (log n)-mu fraction of inputs of length n. In coding theoretic terms, we give a construction of a monotone code that can be uniquely decoded up to error rate 1/4 by a deterministic local decoder.

We construct binary linear codes that are efficiently list- decodable up to a fraction (1/2 - epsiv) of errors. The codes encode k bits into n = poly(k/epsiv) bits and are constructible and list-decodable in time polynomial in k and 1/epsiv (in particular, in our results epsiv need not be constant and can even be polynomially small in n). Our results give the best known polynomial dependence of n on k and 1/epsiv for such codes. Specifically, we are able to achieve n les O(k3/epsiv3+gamma) or, if a linear dependence on k is required, n les O (k/epsiv5+gamma), where gamma > 0 is an arbitrary constant. The best previously known constructive bounds in this setting were n les O(k2/epsiv4) and n les O(k/ epsiv6). Non-constructively, a random linear encoding of length n = O(k/epsiv2) suffices, but no sub-exponential algorithm is known for list decoding random codes. Our construction with a cubic dependence on epsiv is obtained by concatenating the recent Parvaresh-Vardy (PV) codes with dual BCH codes, and crucially exploits the soft decoding algorithm for PV codes. This result yields better hardness results for the problem of approximating NP witnesses in the model of Kumar and Sivakumar. Our result with the linear dependence on k is based on concatenation of the PV code with an arbitrary inner code of good minimum distance. In addition to being a basic question in coding theory, codes that are list-decodable from a fraction (1/2 - epsiv) of errors for epsiv rarr 0 have found many uses in complexity theory. In addition, our codes have the property that all nonzero codewords have relative Hamming weights in the range (1/2 - epsiv, 1/2 + epsiv); this epsiv-biased property is a fundamental notion in pseudorandomness.

We prove that approximating the max. acyclic subgraph problem within a factor better than 1/2 is unique games hard. Specifically, for every constant epsiv > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsiv) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + epsiv) of its edges, then the UGC is false. Note that it is trivial to find an acyclic subgraph with 1/2 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The existence of a rho-approximation algorithmfor rho > 1/2 has been a basic open problem for a while. Our result is the first tight inapproximability result for an ordering problem. The starting point of our reduction isa directed acyclic subgraph (DAG) in which every cut isnearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed by Charikar et al. Using this, we are able to study max. acyclic subgraph, which is a constraint satisfaction problem (CSP) over an unbounded domain, by relating it to a proxy CSP over a bounded domain. The latter is then amenable to powerful techniques based on the invariance principle. Our results also give a super-constant factor inapproximability result for the feedback arc set problem. Using our reductions, we also obtain SDP integrality gapsfor both the problems.

Repeat accumulate accumulate (RAA) codes are turbo-like codes where the message is first repeated k ges 2 times, passed through a first permutation (called interleaver), then an accumulator, then a second permutation, and finally a second accumulator. Bazzi, Mahdian, and Spielman (2003) prove that RAA codes are asymptotically good with high probability when the two permutations are chosen at random. RAA codes admit linear-time encoding algorithms, and are perhaps the simplest known family of linear-time encodable asymptotically good codes. An explicit construction of an asymptotically good RAA code is thus a very interesting goal. We focus on the case when k = 2 and we consider a variation of RAA codes where the inner repeat accumulate code is systematic. We give an explicit construction of the first permutation for which we show that the resulting code is asymptotically good with high probability when the second permutation is chosen at random. The explicit construction uses a cubic Hamiltonian graph with logarithmic girth.

In this paper, we present error-correcting codes that achieve the information-theoretically best possible tradeoff between the rate and error-correction radius. Specifically, for every 0 < R < 1 and epsiv < 0, we present an explicit construction of error-correcting codes of rate that can be list decoded in polynomial time up to a fraction (1- R - epsiv) of worst-case errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are folded Reed-Solomon codes, which are in fact exactly Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in phased bursts. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on epsiv) using existing ideas concerning ldquolist recoveryrdquo and expander-based codes. Concatenating the folded RS codes with suitable inner codes, we get binary codes that can be efficiently decoded up to twice the radius achieved by the standard GMD decoding.

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma, Umans, and Zuckerman (STOC "01) required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS "05). Our expanders can be interpreted as near-optimal "randomness condensers," that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. (STOC "03) and improving upon it when the error parameter is small (e.g. 1/poly(n)).

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an NΩ(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have NO(log logN)-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor NO(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of NΩ(1/c) for c ranging from 1 to Θ((log n)/(log log n)).

A classic result due to Haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field Fq where each equation depends on exactly 3 variables and at least a fraction (1-ε) of the equations can be satisfied, it is NP-hard to satisfy even a fraction (1/q+ε) of the equations.

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the k secrets adversarially, and answers according to this secret. We present an explicit set of O (log N ) questions together with an efficient (i.e., poly(log N ) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small ϵ-biased spaces and the notion of list decoding . We also establish bounds on the number of questions needed to solve the k -secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.

We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (non-obvious) generalization of the approach in the recent breakthrough work of F. Parvaresh and A. Vardy (2005). Our work shows that the PV framework applies to fairly general settings by elucidating the key algebraic concepts underlying it. Also, more importantly, AG codes of arbitrary block length exist over fixed alphabets Sigma, thus enabling us to establish new trade-offs between the list decoding radius and rate over a bounded alphabet size. Similar to algorithms for AG codes from V. Guruswami and M. Sudan (1999, 2001), our encoding/decoding algorithms run in polynomial time assuming a natural polynomial-size representation of the code. For codes based on a specific "optimal" algebraic curve, we also present an expected polynomial time algorithm to construct the requisite representation. This in turn fills an important void in the literature by presenting an efficient construction of the representation often assumed in the list decoding algorithms for AG codes

Learning an unknown halfspace (also called a perceptron) from, labeled examples is one of the classic problems in machine learning. In the noise-free case, when a half-space consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction (1 - epsiv) of the examples exists (for some small constant epsiv > 0), it was not known how to efficiently find a halfspace that is correct on even 51% of the examples. Nor was a hardness result that ruled out getting agreement on more than 99.9% of the examples known. In this work, we close this gap in our understanding, and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary epsiv,delta > 0, we prove that given a set of examples-label pairs from the hypercube a fraction (1 - epsiv) of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction (frac12 + delta) of the examples. The hardness result is tight since it is trivial to get agreement on frac12 the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by Blum et. al in their work on learning halfspaces in the presence of random classification noise (A. Blum et. al, 1996), and in some more recent works as well. Along the way, we also obtain a strong hardness for another basic computational problem: solving a linear system over the rationals

This is a brief survey into the applications of list decoding in complexity theory, specifically in relating the worst-case and average-case complexity of computational problems, and in construction of pseudorandom generators. Since we do not have space for full proofs, the aim is to give a flavor of the utility of list decoding in these settings together with pointers to where further details can be found.

For every 0 < R < 1 and ε > 0, we present an explicit construction of error-correcting codes of rate R that can be list decoded in polynomial time up to a fraction (1-R-ε) of errors. These codes achieve the "capacity" for decoding from adversarial errors, i.e., achieve the optimal trade-off between rate and error-correction radius. At least theoretically, this meets one of the central challenges in coding theory.Prior to this work, explicit codes achieving capacity were not known for any rate R. In fact, our codes are the first to beat the error-correction radius of 1-√R, that was achieved for Reed-Solomon (RS) codes in [9], for all rates R. (For rates R < 1/16, Parvaresh and Vardy [12] had recently improved upon the 1-√R bound; for R → 0, their algorithm can decode a fraction 1-O(R log(1/R)) of errors.)Our codes are simple to describe --- they are certain folded Reed-Solomon codes, which are in fact exactly RS codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, since the codes we propose are not too far from the ones in actual use.The main insight in our work is that some carefully chosen folded RS codes are "compressed" versions of a related family of Parvaresh-Vardy codes. Further, the decoding of the folded RS codes can be reduced to list decoding the related Parvaresh-Vardy codes. The alphabet size of these folded RS codes is polynomial in the block length. This can be reduced to a constant that depends on the distance ε to capacity using ideas concerning "list recovering" and expander-based codes from [7, 8]. Concatenating the folded RS codes with suitable inner codes also gives us polytime constructible binary codes that can be efficiently list decoded up to the Zyablov bound.

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. 1) Given n distinct elements alpha1,...,alphanfrom a field F, and n subsets S1,...,Snof F, each of size at most l, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(alphai)isinSifor every i, as long as ldeltafor small enough delta, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2-epsi)k locations, for any desired epsi>0 (agreement of k is trivial to achieve). Such a bound was known earlier only for a nonexplicit center. Finding explicit bad list decoding configurations is of significant interest-for example, the best known rate versus distance tradeoff, due to Xing, is based on a bad list decoding configuration for algebraic-geometric codes, which is unfortunately not explicitly known

We study the complexity of approximating Max NM-E3SAT, a variant of Max 3SAT when the instances are guaranteed to not have any mixed clauses, i.e., every clause has either all its literals unnegated or all of them negated. This is a natural special case of Max 3SAT introduced Guruswami (2004), where the question of whether this variant can be approximated within a factor better than 7/8 was also posed. We prove that it is NP-hard to approximate Max NM-E3SAT within a factor of 7/8 + /spl epsiv/ for arbitrary /spl epsiv/ > 0, and thus this variant is no easier to approximate than general Max 3SAT. The proof uses the technique of multilayered PCPs, introduced by Dinur et al. (2003), to avoid the technical requirement of folding of the proof tables. Circumventing this requirement means that the PCP verifier can use the bits it accesses without additional negations, and this leads to a hardness for Max 3SAT without any mixed clauses.

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes.

We initiate the study of the computational complexity of the covering radius problem for lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices. For the covering radius on n-dimensional lattices, we show that the problem can be approximated within any constant factor γ(n) > 1 in random exponential time 2 O(n). We also prove that suitably defined gap versions of the problem lie in AM for λ(n) = 2, in coAM for $$ \gamma (n) = {\sqrt {n/\log n} }, $$ and in NP ∩ coNP for $$ \gamma (n) = {\sqrt n }. $$ For the covering radius on n-dimensional linear codes, we show that the problem can be solved in deterministic polynomial time for approximation factor $$ \gamma (n) = \log n, $$ but cannot be solved in polynomial time for some $$ \gamma (n) = \Omega (\log \log n) $$ unless NP can be simulated in deterministic $$ n^{{O(\log \log \log n)}} $$ time. Moreover, we prove that the problem is NP-hard for any constant approximation factor, it is Π2-hard for some constant approximation factor, and that it is unlikely to be Π2-hard for approximation factors larger than 2 (by giving an AM protocol for the appropriate gap problem). This is a natural hardness of approximation result in the polynomial hierarchy. For the shortest independent vectors problem, we give a coAM protocol achieving approximation factor $$ \gamma (n) = {\sqrt {n/\log n} }, $$ solving an open problem of Blömer and Seifert (STOC’99), and prove that the problem is also in coNP for $$ \gamma (n) = {\sqrt n }. $$ Both results are obtained by giving a gap-preserving nondeterministic polynomial time reduction to the closest vector problem.

Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyperedge. We present a new multilayered probabilistically checkable proof (PCP) construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within a factor of $(k-1-\epsilon)$ for arbitrary constants $\epsilon>0$ and $k\ge 3$. The result is nearly tight as this problem can be easily approximated within factor k. Our construction makes use of the biased long-code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets. We also give a different proof that shows an inapproximability factor of $\lfloor \frac{k}{2} \rfloor -\eps$. In addition to being simpler, this proof also works for superconstant values of k up to (log N) 1/c , where c > 1 is a fixed constant and N is the number of hyperedges.

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1-r-/spl epsiv/)/2 of errors over an alphabet of constant size depending only on /spl epsiv/, for every 00. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the Zyablov bound, and also the more general Blokh-Zyablov bound (by resorting to multilevel concatenation). Our work also yields linear-time encodable/decodable codes which match Forney's error exponent for concatenated codes for communication over the binary symmetric channel. The encoding/decoding complexity was quadratic in Forney's result, and Forney's bound has remained the best constructive error exponent for almost 40 years now. In summary, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear-time encoding and decoding algorithms.

Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.

We initiate the study of the computational complexity of the covering radius problem for point lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices. For the covering radius on n-dimensional lattices, we show that the problem can be approximated within any constant factor /spl gamma/(n) > 1 in random exponential time 2/sup O(n)/, it is in AM for /spl gamma/(n) = 2, in coAM for /spl gamma/(n) = /spl radic/(n log n), and in NP /spl cap/ coNP for /spl gamma/(n) = /spl radic/n. For the covering radius on n-dimensional linear codes, we show that the problem can be solved in deterministic polynomial time for approximation factor /spl gamma/(n) = log n, but cannot be solved in polynomial time for some /spl gamma/(n) = /spl Omega/(log log n) unless NP can be simulated in deterministic n/sup O(log log log n)/ time. Moreover, we prove that the problem is NP-hard for every constant approximation factor, it is /spl Pi//sub 2/-hard for some constant approximation factor, and it is in AM for approximation factor 2. So, it is unlikely to be /spl Pi//sub 2/-hard for approximation factors larger than 2. This is a natural hardness of approximation result in the polynomial hierarchy. For the shortest independent vectors problem, we give a coAM protocol achieving approximation factor /spl gamma/(n) = /spl radic/(n/log n), solving an open problem of Blomer and Seifert (1999), and prove that the problem is also in coNP for /spl gamma/(n) = /spl radic/n. Both results are obtained by giving a gap-preserving nondeterministic polynomial time reduction to the closest vector problem.

We present an explicit construction of codes that can be list decoded from a fraction (1-ε) of errors in sub-exponential time and which have rate ε/logO(1)(1/ε). This comes close to the optimal rate of Ω(ε), and is the first sub-exponential complexity construction to beat the rate of ε2 achieved by Reed-Solomon or algebraic-geometric codes. Our construction is based on recent extractor constructions with very good seed length [17]. While the "standard" way of viewing extractors as codes (as in [16]) cannot beat the O(ε2) rate barrier due to the 2 log (1/ε) lower bound on seed length for extractors, we use such extractor codes as a component in a well-known expander-based construction scheme to get our result. The O(ε2) rate barrier also arises if one argues about list decoding using the minimum distance (via the so-called Johnson bound) --- so this also gives the first explicit construction that "beats the Johnson bound" for list decoding from errors.The main message from our work is perhaps conceptual, namely that good strong extractors for low min-entropies will yield near-optimal list decodable codes. Given all the progress that has been made on extractors, we view this as an optimistic avenue to look for better list decodable codes, both by looking for better explicit extractor constructions, as well as by importing non-trivial techniques from the extractor world in reasoning about and constructing codes.

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just 4 colors. This result is already known , [S. Khanna, N. Linial, and S. Safra, Combinatorica, 20 (2000), pp. 393--415], but our proof is novel because it does not rely on the PCP theorem, while the known one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor $n^{\epsilon}$ hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem [M. Bellare, O. Goldreich, and M. Sudan, SIAM J. Comput., 27 (1998), pp. 805--915]. Another aspect in which our proof is novel is in its use of the PCP theorem to show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction of Khanna, Linial, and Safra). We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires $n^{\Omega(1)}$ colors. Our proof technique also shows that there is an $\varepsilon_0 > 0$ such that it is NP-hard to legally 4-color even a $(1-\varepsilon_0)$ fraction of the edges of a 3-colorable graph.

Under list decoding of error-correcting codes, the decoding algorithm is allowed to output a small list of codewords that are close to the noisy received word. This relaxation permits recovery even under very high noise thresholds. We consider one possible scenario that would permit disambiguating between the elements of the list, namely where the sender of the message provides some hopefully small amount of side information about the transmitted message on a separate auxiliary channel that is noise-free. This setting becomes meaningful and useful when the amount of side information that needs to be communicated is much smaller than the length of the message. We study what kind of side information is necessary and sufficient in the above context. The short, conceptual answer is that the side information must be randomized and the message recovery is with a small failure probability. Specifically, we prove that deterministic schemes, which guarantee correct recovery of the message, provide no savings and essentially the entire message has to be sent as side information. However there exist randomized schemes, which only need side information of length logarithmic in the message length. In fact, in the limit of repeated communication of several messages, amortized amount of side information needed per message can be a constant independent of the message length or the failure probability. Concretely, we can correct up to a fraction (1/2-/spl gamma/) of errors for binary codes using only 2log(1//spl gamma/)+O(1) amortized bits of side information per message, and this is in fact the best possible (up to additive constant terms).

We consider the problem of clustering a collection of elements based on pairwise judgments of similarity and dissimilarity. N. Bansal et al. (2002) cast the problem thus: given a graph G whose edges are labeled "+" (similar) or "-" (dissimilar), partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the input labeling is maximized (resp. minimized). Complete graphs, where the classifier labels every edge, and general graphs, where some edges are not labeled, are both worth studying. We answer several questions left open by N. Bansal et al. (2002) and provide a sound overview of clustering with qualitative information. We give a factor 4 approximation for minimization on complete graphs, and a factor O(log n) approximation for general graphs. For the maximization version, a PTAS for complete graphs is shown by N. Bansal et al. (2002); we give a factor 0.7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.

Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k-1-ε) for any k ≥ 3 and any ε>0. The result is essentially tight as this problem can be easily approximated within factor k. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.

We present the first construction of error-correcting codes which can be (list) decoded from a noise fraction arbitrarily close to 1 in linear time. Specifically, we present an explicit construction of codes which can be encoded in linear time as well as list decoded in linear time from a fraction (1-ε) of errors for arbitrary ε > 0. The rate and alphabet size of the construction are constants that depend only on ε. Our construction involves devising a new combinatorial approach to list decoding, in contrast to all previous approaches which relied on the power of decoding algorithms for algebraic codes like Reed-Solomon codes.Our result implies that it is possible to have, and in fact explicitly specifies, a coding scheme for arbitrarily large noise thresholds with only constant redundancy in the encoding and constant amount of work (at both the sending and receiving ends) for each bit of information to be communicated. Such a result was known for certain probabilistic error models, and here we show that this is possible under the stronger adversarial noise model as well.

We consider the problem of list decoding from erasures. We establish lower and upper bounds on the rate of a (binary linear) code that can be list decoded with list size L when up to a fraction p of its symbols are adversarially erased. Such bounds already exist in the literature, albeit under the label of generalized Hamming weights, and we make their connection to list decoding from erasures explicit. Our bounds show that in the limit of large L, the rate of such a code approaches the "capacity" (1 - p) of the erasure channel. Such nicely list decodable codes are then used as inner codes in a suitable concatenation scheme to give a uniformly constructive family of asymptotically good binary linear codes of rate /spl Omega/(/spl epsiv//sup 2//log(1//spl epsiv/)) that can be efficiently list-decoded using lists of size O(1//spl epsiv/) when an adversarially chosen (1 - /spl epsiv/) fraction of symbols are erased, for arbitrary /spl epsiv/ > 0. This improves previous results in this vein, which achieved a rate of /spl Omega/(/spl epsiv//sup 3/log(1//spl epsiv/)).

We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.

We consider the problem of the best possible relation between the list decodability of a binary linear code and its minimum distance. We prove, under a widely-believed number-theoretic conjecture, that the classical "Johnson bound" gives, in general, the best possible relation between the list decoding radius of a code and its minimum distance. The analogous result is known to hold by a folklore random coding argument for the case of non-linear codes, but the linear case is more subtle and has remained open.We prove our result by exhibiting an infinite family of binary linear codes of "large" minimum distance with a super-polynomial number (in blocklength) of codewords all within a Hamming ball of radius close to the Johnson bound. Even the existence of codes with a super-polynomial number of codewords in a ball of radius bounded away from the minimum distance (let alone radius close to the Johnson bound) was open prior to our work. We also unconditionally prove the "tightness" of the Johnson bound for decoding with list size that is an arbitrarily large constant.

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1 —rε)/2 of errors over an alphabet of constant size depending only on ε, for every 0 < r < 1 and arbitrarily small ε> 0. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures [2]; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the so-called "Zyablov bound". In a nutshell, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear time encoding and decoding algorithms.We also obtain some results for list decoding targeted at the situation when the fraction of errors is very large, namely (1—ε) for an arbitrarily small constant ε > 0. The previously known constructions of such codes of good rate over constant-sized alphabets either used algebraic-geometric codes and thus suffered from complicated constructions and slow decoding, or as in the recent work of the authors [9], had fast encoding/decoding, but suffered from an alphabet size that was exponential in 1/ε. We present two constructions of such codes with rate close to Ω(ε2) over an alphabet of size quasi-polynomial in 1/ε. One of the constructions, at the expense of a slight worsening of the rate, can achieve an alphabet size which is polynomial in 1/ε. It also yields constructions of codes for list decoding from erasures which achieve new trade-offs. In particular, we construct codes of rate close to the optimal Ω(ε) rate which can be efficiently list decoded from a fraction (1—ε) of erasures.

We introduce the notion of covering complexity of a verifier for probabilistically checkable proofs (PCPs). Such a verifier is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The verifier is also given a random string and decides whether to accept the proof or not, based on the given random string. We define the covering complexity of such a verifier, on a given input, to be the minimum number of proofs needed to "satisfy" the verifier on every random string; i.e., on every random string, at least one of the given proofs must be accepted by the verifier. The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems and, in particular, (hyper)graph coloring problems. We present a PCP verifier for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a superconstant covering complexity for statements not in the language. Moreover, the acceptance predicate of this verifier is a simple not-all-equal check on the four bits it reads. This enables us to prove that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption.

Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. We report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H/sup -1/(1-R-1/c)/spl middot/n. This answers the main open question from the work of Elias (1957). This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan (see IEEE Trans. Inform. Theory, vol.45, p.1757-67, Sept. 1999, and Proc. 32nd ACM Symp. Theory of Computing (STOC), Portland, OR, p. 181-190, May 2000) in this vein. Specifically, for every /spl epsi/ > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate /spl Omega/(/spl epsi//sup 4/) that can be list-decoded in polynomial time from up to a fraction (1/2-/spl epsi/) of errors, using lists of size O(/spl epsi//sup -2/). On the negative side, we show that for every /spl delta/ and c, there exists /spl tau/0, and an infinite family of linear codes {C/sub i/}/sub i/ such that if n/sub i/ denotes the block length of C/sub i/, then C/sub i/ has minimum distance at least /spl delta/ /spl middot/ n/sub i/ and contains more than c/sub 1/ /spl middot/ n/sub i//sup c/ codewords in some Hamming ball of radius /spl tau/ /spl middot/ n/sub i/. While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the "radius for list-decodability by a polynomial-sized list" away from the minimum distance of the code.

We present several novel constructions of codes which share the common thread of using expander (or expander-like) graphs as a component. The expanders enable the design of efficient decoding algorithms that correct a large number of errors through various forms of "voting" procedures. We consider both the notions of unique and list decoding, and in all cases obtain asymptotically good codes which are decodable up to a "maximum" possible radius and either: (a) achieve a similar rate as the previously best known codes but come with significantly faster algorithms, or (b) achieve a rate better than any prior construction with similar error-correction properties. Among our main results are: i) codes of rate /spl Omega/(/spl epsi//sup 2/) over constant-sized alphabet that can be list decoded in quadratic time from (1-/spl epsi/) errors; ii) codes of rate /spl Omega/(/spl epsi/) over constant-sized alphabet that can be uniquely decoded from (1/2-/spl epsi/) errors in near-linear time (this matches AG-codes with much faster algorithms); iii) linear-time encodable and decodable binary codes of positive rate (in fact, rate /spl Omega/(/spl epsi//sup 2/)) that can correct up to (1/4-/spl epsi/) fraction errors.

We show that all algebraic-geometric codes possess a succinct representation that allows for list decoding algorithms to run in polynomial time. We do this by presenting a root-finding algorithm for univariate polynomials over function fields when their coefficients lie in finite-dimensional linear spaces, and proving that there is a polynomial size representation, given which the root-finding algorithm runs in polynomial time.

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known, but our proof is novel as it does not rely on the PCP theorem. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor n/sup /spl epsiv// hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem. Another aspect in which our proof is different is that using the PCP theorem we can show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction. We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires n/sup /spl Omega/(1)/ colours. Our proof technique also shows that there is an /spl epsi//sub 0/>0 such that it is NP-hard to legally 4-color even a (1-/spl epsi//sub 0/) fraction of the edges of a 3-colorable graph.

Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of multidimensional objects, the goal is to select a subset K of relevant dimensions (or features) such that some desired property /spl Pi/ holds for the set S restricted to K. Depending on /spl Pi/, the goal could be to either maximize or minimize the size of the subset K. Several well-studied feature selection problems can be cast in this form. We study the problems in this class derived from several natural and interesting properties /spl Pi/, including variants of the classical p-center problem as well as problems akin to determining the VC-dimension of a set system. Our main contribution is a theoretical framework for studying combinatorial feature selection, providing (in most cases essentially tight) approximation algorithms and hardness results for several instances of these problems.

We introduce the notion of covering complexity of a probabilistic verifier. The covering complexity of a verifier on a given input is the minimum number of proofs needed to "satisfy" the verifier on every random string, i.e., on every random string, at least one of the given proofs must be accepted by the verifier. The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems, and in particular (hyper)-graph coloring problems. We present a PCP verifier for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a super-constant covering complexity for statements not in the language. Moreover the acceptance predicate of this verifier is a simple Not-all-Equal check on the four bits it reads. This enables us to prove that for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors, and also yields a super-constant inapproximability result under a stronger hardness assumption.

Given n relatively prime integers p/sub 1/, where m/sub i/=m(mod p/sub i/). The soft-decision decoding problem for the Chinese remainder code is given as input a vector of residues r/spl I.oarr/=(r/sub 1/,...,r/sub n/), a vector of weights, and an agreement parameter t. The goal is to find all messages m /spl isin/ M such that the weighted agreement between the encoding of m and r/spl I.oarr/(i.e., /spl Sigma//sub i/ w/sub i/ summed over all i such that r/sub i/=m(mod pi)) is at least t. Here we give a new algorithm for solving the soft-decision problem for the CRT code that works provided the agreement parameter t is sufficiently large. We derive our algorithm by digging deeper into the algebra underlying the error-correcting algorithms and unveiling an "ideal"-theoretic view of decoding. When all weights are equal to 1, we obtain the more commonly studied "list decoding" problem. List decoding algorithms for the Chinese Remainder Code were given recently by O. Goldreich et al. (1999), and improved by D. Boneh. Their algorithms work for t/spl ges//spl radic/(2knlogp/sub n//logp1) and t/spl ges//spl radic/(knlogp/sub n//logp/sub 1/), respectively. We improve upon the algorithms above by using our soft-decision decoding algorithm with a non-trivial choice of weights, solve the list decoding problem provided t/spl ges//spl radic/(k(n+/spl epsi/)), for arbitrarily small /spl epsi//spl ges/0.

We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest "proof" for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework, constructing a set of prices for any AND/OR tree that satisfies a very strong type of equilibrium property.

We give efficient (polynomial-time) list-decoding algorithms for certain families of error-correcting codes obtained by "concatenation".Specifically, we give list-decoding algorithms for codes where the "outer code" is a Reed-Solomon or Algebraic-geometric code and the "inner code" is a Hadamard code.Codes obtained by such concatenation are the best known constructions of errorcorrecting codes with very large minimum distance.Our decoding algorithms enhance their nice combinatorial properties with algorithmic ones, by decoding these codes up to the currently known bound on their list-decoding "capacity".In particular, the number of errors that we can correct matches (exactly) the number of errors for which it is known that the list size is bounded by a polynomial in the length of the codewords.

We focus on methods to solve multiclass learning problems by using only simple and efficient binary learners.We investigate the approach of Dietterich and Bakiri [2] based on error-correcting codes (which we call ECC).We distill ermr COTrelation as one of the key parameters influencing the performance of the ECC approach, and prove upper and lower bounds on the training error of the final hypothesis in terms of the error-correlation between the various binary hypotheses.Boosting is a powerful and well-studied learning technique that appears to annul error correlation disadvantages by cleverly weighting training examples and hypotheses.An interesting algorithm called ADABOOST.OC [12] combines boosting with the ECC approach and gives an algorithm that has the performance advantages of boosting and at the same time relies only on simple binary weak leamers.We propose a variant of this algorithm, which we call ADABoosT.ECC, that, by using a different weighting of the votes of the weak hypotheses, is able to improve on the performance of ADA-BoosT.OC, both theoretically and experimentally, and in addition is arguably a more direct reduction of multiclass learning to binary learning problems than previous multiclass boosting algorithms.

We study the approximability of two classes of network routing problems.The first class of problems in our study corre spend to classical multicommodity flow problems of the following form: We are given a network G with integer capacities on its edges, together with source-sink pairs (a, ti), 1 5 i 2 k, such that a positive integer demand di and a positive "profit" t'i is associated with eah pair.A feasible solution is a subset S of the (sir ti) pairs such that demands associated with pairs in S can be fully met through a routing which respects all capacity constraints, and the objective is to maximize the total profit associated with the satisfied pairs.We consider two natural variants: unsplittable flow (USF) where each pair must be satisfied by routing all its demand on a single

Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: given n points ((x/sub i//spl middot/y/sub i/))/sub i=1//sup n/, x/sub i/, y/sub i//spl isin/F, and a degree parameter k and error parameter e, find all univariate polynomials p of degree at most k such that y/sub i/=p(x/sub i/) for all but at most e values of i/spl isin/(1,...,n). We give an algorithm that solves this problem for e1/3, where the result yields the first asymptotic improvement in four decades. The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n-/spl radic/(n(n-d')) errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of Shokrollahi and Wasserman (see in Proc. 29th Annu. ACM Symp. Theory of Computing, p.241-48, 1998) and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes.

It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-trivial verification power and motivate the task of determining the lowest error that can be achieved with a 3-query PCP. Recently, Hastad (1997) has shown a tight characterization of NP by constructing a 3-query PCP verifier with "error" arbitrarily close to 1/2. Unfortunately this verifier makes two-sided error and Hastad makes essential use of this feature. One-sided error, on the other hand, is a natural notion to associate with a proof system, since it has the desirable property that every rejected proof has a short counterexample. The question of determining the smallest error for which there exists a 3-query PCP verifier making one-sided error and accepting an NP-complete language, however, remained open. We resolve this question by showing that NP has a 3-query PCP with a one-sided error that is arbitrarily close to 1/2. This characterization is tight, i.e., the error cannot be lower. This result is in seeming contradiction with the results of Trevisan (1997) and Zwick (1998) who show that in order to recognize an NP-complete language, the error probability of a PCP verifier making 3 non-adaptive queries and having one-sided error must be at least 5/8. We get around this bottleneck by designing an adaptive 3-query PCP for NP. Our result yields the first tight analysis of an adaptive PCP; and reveals a previously unsuspected separation between the powers of adaptive and non-adaptive PCPs. Our design and analysis of adaptive PCPs can be extended to higher number of queries as well and we give an example of such a proof system with 5 queries. Our adaptive verifiers yield proof systems whose error probabilities match those of previous constructions, while also achieving one-sidedness in the error. This raises new questions about the power of adaptive PCPs, which deserve further study.

Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x/sub i/.y/sub i/)}/sub i=1//sup n/, x/sub i/,y/sub i//spl isin/F, and a degree parameter k and error parameter e, find all univariate polynomials p of degree at most k such that y/sub i/=p(x/sub i/) for all but at most e values of i/spl isin/{1....,n}. We give an algorithm that solves this problem for e1/3, where the result yields the first asymptotic improvement in four decades. The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometric codes. In both cases, we obtain a list decoding algorithm that corrects up to n-/spl radic/(n-d-) errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometric codes extends the methods of Shokrollahi and Wasserman (1998) and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve fitting problem, which is of use in soft-decision decoding algorithms for Reed-Solomon codes.