Venkatesan Guruswami

STOC Conference 2025 Conference Paper

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

• Venkatesan Guruswami
• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Kewen Wu 0001

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 )· n O (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 n k 1− o (1) time. This immediately implies, for example, that finding a ( k /2)-clique in an n -vertex graph with a k -clique requires n k 1− 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.

STOC Conference 2025 Conference Paper

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates

• Louis Golowich
• Venkatesan Guruswami

FOCS Conference 2025 Conference Paper

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

• Vijay Bhattiprolu
• Venkatesan Guruswami
• Euiwoong Lee
• Xuandi Ren

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.

FOCS Conference 2025 Conference Paper

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks

• Louis Golowich
• Venkatesan Guruswami

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.

SODA Conference 2025 Conference Paper

Quantum Locally Recoverable Codes

• Louis Golowich
• Venkatesan Guruswami

STOC Conference 2025 Conference Paper

Redundancy Is All You Need

• Joshua Brakensiek
• Venkatesan Guruswami

SODA Conference 2024 Conference Paper

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

• Omar Alrabiah
• Venkatesan Guruswami
• Ray Li

FOCS Conference 2024 Conference Paper

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold

• Venkatesan Guruswami
• Jun-Ting Hsieh
• Prasad Raghavendra

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.

FOCS Conference 2024 Conference Paper

Decoding Quasi-Cyclic Quantum LDPC Codes

• Louis Golowich
• Venkatesan Guruswami

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.

FOCS Conference 2024 Conference Paper

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

• Omar Alrabiah
• Venkatesan Guruswami

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.

STOC Conference 2024 Conference Paper

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

• Venkatesan Guruswami
• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Kewen Wu 0001

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.

STOC Conference 2024 Conference Paper

Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields

• Omar Alrabiah
• Venkatesan Guruswami
• Ray Li

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 2 O ( 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 ( n 2 ). 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 2 O (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.

STOC Conference 2023 Conference Paper

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

• Omar Alrabiah
• Venkatesan Guruswami
• Pravesh K. Kothari
• Peter Manohar

A code C ∶ {0,1} k → {0,1} n is a q -locally decodable code ( q -LDC) if one can recover any chosen bit b i 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( k o (1) ), while the best known results only show a quadratic lower bound n ≥ Ω( k 2 /log( k )) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ Ω( k 3 /log 6 ( k )) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k . Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

STOC Conference 2023 Conference Paper

Binary Error-Correcting Codes with Minimal Noiseless Feedback

• Meghal Gupta
• Venkatesan Guruswami
• Rachel Yun Zhang

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. 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 є > 0, we construct a coding scheme that tolerates a fraction 1/3−є of bit flips relying only on O є (log k ) bits of feedback from Bob sent in a fixed O є (1) number of rounds. We complement this with a matching lower bound showing that Ω(log k ) bits of feedback are necessary to recover from an error fraction exceeding 1/4 (the threshold without any feedback), and for schemes resilient to a fraction 1/3−є of bit flips, the number of rounds must grow as є → 0. We also study (and resolve) the question for the simpler model of erasures. We show that O є (log k ) bits of feedback spread over O є (1) rounds suffice to tolerate a fraction (1−є) of erasures. Likewise, our Ω(log k ) lower bound applies for erasure fractions exceeding 1/2, and an increasing number of rounds are required as the erasure fraction approaches 1.

FOCS Conference 2023 Conference Paper

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

• Venkatesan Guruswami
• Jun-Ting Hsieh
• Pravesh K. Kothari
• Peter Manohar

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.

STOC Conference 2023 Conference Paper

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms

• Huck Bennett
• Mahdi Cheraghchi
• Venkatesan Guruswami
• João Ribeiro 0002

STOC Conference 2023 Conference Paper

SDPs and Robust Satisfiability of Promise CSP

• Joshua Brakensiek
• Venkatesan Guruswami
• Sai Sandeep

STOC Conference 2022 Conference Paper

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

• Venkatesan Guruswami
• Pravesh K. Kothari
• Peter Manohar

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 also make a surprising connection between the analysis of our refutation algorithm in the significantly ”randomness starved” setting of semi-random k-XOR and the existence of even covers in worst-case hypergraphs. We use this connection to positively resolve Feige’s 2008 conjecture – an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the ”spectral threshold” of n^(k/2), extending the celebrated result for random 3-SAT of Feige, Kim and Ofek.

SODA Conference 2022 Conference Paper

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

• Venkatesan Guruswami
• Sai Sandeep

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.

FOCS Conference 2022 Conference Paper

Punctured Low-Bias Codes Behave Like Random Linear Codes

• Venkatesan Guruswami
• Jonathan Mosheiff

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.

SODA Conference 2021 Conference Paper

Efficient Linear and Affine Codes for Correcting Insertions/Deletions

• Kuan Cheng
• Venkatesan Guruswami
• Bernhard Haeupler
• Xin Li 0006

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.

SODA Conference 2021 Conference Paper

Explicit two-deletion codes with redundancy matching the existential bound

• Venkatesan Guruswami
• Johan Håstad

We give an explicit construction of length- n binary codes capable of correcting the deletion of two bits that have size 2 n / n 4+ 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 Ω(2 n / n 4 ). 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 Ω(2 n / n 3+ 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.

SODA Conference 2021 Conference Paper

Strongly refuting all semi-random Boolean CSPs

• Jackson Abascal
• Venkatesan Guruswami
• Pravesh K. Kothari

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 Õ ( n k / 2 ) constraints. (In a semi-random k -XOR instance, the equations can be arbitrary and only the right hand sides are random.) One of our key insights is to identify a simple combinatorial property of random XOR instances that makes spectral refutation work. Our approach involves taking an instance that does not satisfy this property (i. e. , is 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.

FOCS Conference 2021 Conference Paper

The zero-rate threshold for adversarial bit-deletions is less than 1/2

• Venkatesan Guruswami
• Xiaoyu He
• Ray Li

We prove that there exists an absolute constant 6 > 0 such any binary code $C$ ⊂ {0, 1} N tolerating (1/2 - δ) $N$ adversarial deletions must satisfy| C| ≤ 2 polylog $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 2 log A N 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.

STOC Conference 2020 Conference Paper

Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity

• Venkatesan Guruswami
• Andrii Riazanov
• Min Ye 0005

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.

STOC Conference 2020 Conference Paper

Optimally resilient codes for list-decoding from insertions and deletions

• Venkatesan Guruswami
• Bernhard Haeupler
• Amirbehshad Shahrasbi

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?”

SODA Conference 2020 Conference Paper

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs

• Joshua Brakensiek
• Venkatesan Guruswami

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.

SODA Conference 2019 Conference Paper

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs

• Joshua Brakensiek
• Venkatesan Guruswami

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.

STOC Conference 2019 Conference Paper

An exponential lower bound on the sub-packetization of MSR codes

• Omar Alrabiah
• Venkatesan Guruswami

SODA Conference 2019 Conference Paper

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

• Vijay Bhattiprolu
• Mrinalkanti Ghosh
• Venkatesan Guruswami
• Euiwoong Lee
• Madhur Tulsiani

We study the problem of computing the p → q operator norm of a matrix A in ℝ m × n, defined as ‖ A ‖ p → q: = sup x ∊ℝ 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 2 O ( log 1−∊ n ) assuming NP is not contained in BPTIME(2 log O(1) n ) ).

STOC Conference 2019 Conference Paper

Bridging between 0/1 and linear programming via random walks

• Joshua Brakensiek
• Venkatesan Guruswami

Under the Strong Exponential Time Hypothesis, an integer linear program with n Boolean-valued variables and m equations cannot be solved in c n 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 O E ((2−measure( E )) n poly( n , m )) that finds a solution in E n 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 2 n to polynomial. Taking E = [0,1/ k ) ∪ (1−1/ k ,1] in our result yields as a corollary a randomized (2−2/ k ) n poly( n ) time algorithm for k -SAT. While our approach has some high level resemblance to Sch'oning’s beautiful algorithm, our general algorithm is based on a more sophisticated random walk that incorporates several new ingredients, such as a multiplicative potential to measure progress, a judicious choice of starting distribution, and a time varying distribution for the evolution of the random walk that is itself computed via an LP at each step (a solution to which is guaranteed based on the minimax theorem). Plugging the LP algorithm into our earlier polymorphic framework yields fast exponential algorithms for any CSP (like k -SAT, 1-in-3-SAT, NAE k -SAT) that admit so-called “threshold partial polymorphisms.”

STOC Conference 2019 Conference Paper

CSPs with global modular constraints: algorithms and hardness via polynomial representations

• Joshua Brakensiek
• Sivakanth Gopi
• Venkatesan Guruswami

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. The inspiration for our study comes from a recent work by N'agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kind 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 .

SODA Conference 2019 Conference Paper

Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities

• Sivakanth Gopi
• Venkatesan Guruswami
• Sergey Yekhanin

SODA Conference 2018 Conference Paper

Coding against deletions in oblivious and online models

• Venkatesan Guruswami
• Ray Li

STOC Conference 2018 Conference Paper

General strong polarization

• Jaroslaw Blasiok
• Venkatesan Guruswami
• Preetum Nakkiran
• Atri Rudra
• Madhu Sudan 0001

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 G 2 = ( [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.

SODA Conference 2018 Conference Paper

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy

• Joshua Brakensiek
• Venkatesan Guruswami

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 F 2 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.

SODA Conference 2017 Conference Paper

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth

• Venkatesan Guruswami
• Ankit Singh Rawat

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.

FOCS Conference 2017 Conference Paper

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

• Vijay Bhattiprolu
• Mrinalkanti Ghosh
• Venkatesan Guruswami
• Euiwoong Lee
• Madhur Tulsiani

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).

SODA Conference 2016 Conference Paper

An improved bound on the fraction of correctable deletions

• Boris Bukh
• Venkatesan Guruswami

SODA Conference 2016 Conference Paper

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

• Joshua Brakensiek
• Venkatesan Guruswami
• Samuel Zbarsky

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 ≈ 2 n / n codewords of length n, i. e. , at most log n bits of redundancy. However, even for the case of two deletions, there was no known explicit construction with redundancy less than n Ω(1). For any fixed k, we construct a binary code with c k log n redundancy that can be decoded from k deletions in O k ( n log 4 n ) time. The coefficient c k can be taken to be O ( k 2 log k ), which is only quadratically worse than the optimal, non-constructive bound of O ( k ). We also indicate how to modify this code to allow for a combination of up to k insertions and deletions. We also note that among linear codes capable of correcting k deletions, the ( k + 1)-fold repetition code is essentially the best possible.

SODA Conference 2016 Conference Paper

Nearly Optimal NP-Hardness of Unique Coverage

• Venkatesan Guruswami
• Euiwoong Lee

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/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 Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence.

STOC Conference 2016 Conference Paper

Repairing Reed-solomon codes

• Venkatesan Guruswami
• Mary Wootters

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.

FOCS Conference 2016 Conference Paper

Robust Fourier and Polynomial Curve Fitting

• Venkatesan Guruswami
• David Zuckerman

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 (x i, y i ) ε [-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(x i ) - y i |≤ δ. 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 x i or arbitrary x i that are roughly equally spaced, or in the algebraic setting when the x i are chosen according to the Chebyshev distribution, and N = Õ(d2) in the algebraic setting with random (or roughly equally spaced) x i.

SODA Conference 2015 Conference Paper

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

• Venkatesan Guruswami
• Madhu Sudan 0001
• Ameya Velingker
• Carol Wang

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.

SODA Conference 2015 Conference Paper

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

• Venkatesan Guruswami
• Euiwoong Lee

FOCS Conference 2014 Conference Paper

(2 + epsilon)-Sat Is NP-Hard

• Per Austrin
• Johan Håstad
• Venkatesan Guruswami

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.

SODA Conference 2014 Conference Paper

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

• Venkatesan Guruswami
• Chaoping Xing

STOC Conference 2014 Conference Paper

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

• Venkatesan Guruswami
• Prahladh Harsha
• Johan Håstad
• Srikanth Srinivasan 0001
• Girish Varma

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.

SODA Conference 2013 Conference Paper

Approximating Non-Uniform Sparsest Cut Via Generalized Spectra

• Venkatesan Guruswami
• Ali Kemal Sinop

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 2 r / (δε) 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.

FOCS Conference 2013 Conference Paper

Explicit Subspace Designs

• Venkatesan Guruswami
• Swastik Kopparty

A subspace design is a collection {H 1, H 2, .. ., H M } of subspaces of F m q with the property that no low-dimensional subspace W of F q m intersects 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 P W that has several roots for each H that non-trivially intersects W. The construction of P W is 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.

STOC Conference 2013 Conference Paper

List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound

• Venkatesan Guruswami
• Chaoping Xing

FOCS Conference 2013 Conference Paper

PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring

• Irit Dinur
• Venkatesan Guruswami

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 β: F 2 m → F 2 is 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.

FOCS Conference 2013 Conference Paper

Polar Codes: Speed of Polarization and Polynomial Gap to Capacity

• Venkatesan Guruswami
• Patrick Xia 0001

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.

SODA Conference 2013 Conference Paper

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

• Mahdi Cheraghchi
• Venkatesan Guruswami
• Ameya Velingker

We prove that a random linear code over F q, with probability arbitrarily close to 1, is list decodable at radius 1 − 1/ q − ∊ with list size L = O (1/∊ 2 ) and rate R = Ω q (∊ 2 /(log 3 (1/∊))). Up to the polylogarithmic factor in 1/∊ and constant factors depending on q, this matches the lower bound L = Ω q (1/∊ 2 ) for the list size and upper bound R = O q (∊ 2 ) for the rate. Previously only existence (and not abundance) of such codes was known for the special case q = 2 (Guruswami, Håstad, Sudan and Zuckerman, 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 (RIP-2). 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 ) 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.

SODA Conference 2012 Conference Paper

Bypassing UGC from some optimal geometric inapproximability results

• Venkatesan Guruswami
• Prasad Raghavendra
• Rishi Saket
• Yi Wu 0002

FOCS Conference 2012 Conference Paper

Faster SDP Hierarchy Solvers for Local Rounding Algorithms

• Venkatesan Guruswami
• Ali Kemal Sinop

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 n O(1) 2 O(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 n O(1) 2 O(r) time algorithms to obtain the same guarantees in many cases as the earlier n O(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 n O(1) 2 O(r) time, where λ r is the r'th smallest eigenvalue of the graph's normalized Laplacian; (ii) a similar guarantee in n O(1) k O(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 (n2 r ) 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.

STOC Conference 2012 Conference Paper

Folded codes from function field towers and improved optimal rate list decoding

• Venkatesan Guruswami
• Chaoping Xing

SODA Conference 2012 Conference Paper

Optimal column-based low-rank matrix reconstruction

• Venkatesan Guruswami
• Ali Kemal Sinop

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 ( rnm 2 ) arithmetic operations.

SODA Conference 2012 Conference Paper

Polynomial integrality gaps for strong SDP relaxations of Densest k -subgraph

• Aditya Bhaskara
• Moses Charikar
• Aravindan Vijayaraghavan
• Venkatesan Guruswami
• Yuan Zhou 0007

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 ( n 1/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 Ω( n 1/4 /log 3 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 n 2/53 − ∊ on the integrality gap of n Ω(∊) rounds of the Lasserre SDP relaxation for Densest k -subgraph, and an n Ω ∊ (1) gap for n 1−∊ 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 n 1/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.

FOCS Conference 2011 Conference Paper

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

• Venkatesan Guruswami
• Ali Kemal Sinop

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 n O(r/ε2) with approximation ratio (1+ε)/min{1, λ r }, where λ r is 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 n O(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 n O(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).

SODA Conference 2011 Conference Paper

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

• Venkatesan Guruswami
• Ali Kemal Sinop

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.

SODA Conference 2011 Conference Paper

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set

• Venkatesan Guruswami
• Yuan Zhou 0007

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. 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. 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.

FOCS Conference 2010 Conference Paper

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

• Venkatesan Guruswami
• Adam Smith 0006

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 N c, assuming the existence of pseudorandom generators.

STOC Conference 2010 Conference Paper

On the list-decodability of random linear codes

• Venkatesan Guruswami
• Johan Håstad
• Swastik Kopparty

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 F q , p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in F q n 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-H q (p). The best previously known list-size bound was q O(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known).

FOCS Conference 2009 Conference Paper

Agnostic Learning of Monomials by Halfspaces Is Hard

• Vitaly Feldman
• Venkatesan Guruswami
• Prasad Raghavendra
• Yi Wu 0002

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.

STOC Conference 2009 Conference Paper

Artin automorphisms, cyclotomic function fields, and folded list-decodable codes

• Venkatesan Guruswami

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 ∈ F q [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.

STOC Conference 2009 Conference Paper

List decoding tensor products and interleaved codes

• Parikshit Gopalan
• Venkatesan Guruswami
• Prasad Raghavendra

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. Our results give better bounds on the list decoding radius than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson bound.

STOC Conference 2009 Conference Paper

MaxMin allocation via degree lower-bounded arborescences

• MohammadHossein Bateni
• Moses Charikar
• Venkatesan Guruswami

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 p ij 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 ~O(√ 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.

SODA Conference 2008 Conference Paper

Almost Euclidean subspaces of l N 1 via expander codes

• Venkatesan Guruswami
• James R. Lee
• Alexander A. Razborov

FOCS Conference 2008 Conference Paper

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

• Venkatesan Guruswami
• Rajsekar Manokaran
• Prasad Raghavendra

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.

SODA Conference 2008 Conference Paper

Concatenated codes can achieve list-decoding capacity

• Venkatesan Guruswami
• Atri Rudra

STOC Conference 2007 Conference Paper

A 3-query PCP over integers

• Venkatesan Guruswami
• Prasad Raghavendra

A classic result due to Haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field F q 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. In this work, we prove the analog of Håstad's result for equations over the integers (as well as the reals). Formally, we prove that for every ε,δ > 0, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is NP-hard to distinguish between the following two cases: (i) There is an assignment of integer values to the variables that satisfies at least a fraction (1-ε) of the equations, and (ii) No assignmenteven of real values to the variables satisfies more than a fraction δ of the equations.

STOC Conference 2007 Conference Paper

Hardness of routing with congestion in directed graphs

• Julia Chuzhoy
• Venkatesan Guruswami
• Sanjeev Khanna
• Kunal Talwar

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 N O(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 N O(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)).

FOCS Conference 2006 Conference Paper

Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets

• Venkatesan Guruswami
• Anindya C. Patthak

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

SODA Conference 2006 Conference Paper

Correlation clustering with a fixed number of clusters

• Ioannis Giotis 0001
• Venkatesan Guruswami

STOC Conference 2006 Conference Paper

Explicit capacity-achieving list-decodable codes

• Venkatesan Guruswami
• Atri Rudra

For every 0 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.

FOCS Conference 2006 Conference Paper

Hardness of Learning Halfspaces with Noise

• Venkatesan Guruswami
• Prasad Raghavendra

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

STOC Conference 2005 Conference Paper

Limits to list decoding Reed-Solomon codes

• Venkatesan Guruswami
• Atri Rudra

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. Given n distinct elements α 1 ,...,α n from a field F, and n subsets S 1 ,...,S n of F each of size at most l, the list decoding algorithm of Guruswami and Sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(α i ) ∈ S i for every i, as long as l √k n'. By our result, an improvement to the Reed-Solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the β i 's (for example, their (near) distinctness).

SODA Conference 2005 Conference Paper

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

• Venkatesan Guruswami
• Alexander Vardy

SODA Conference 2005 Conference Paper

On profit-maximizing envy-free pricing

• Venkatesan Guruswami
• Jason D. Hartline
• Anna R. Karlin
• David Kempe 0001
• Claire Mathieu
• Frank McSherry

STOC Conference 2004 Conference Paper

Better extractors for better codes?

• Venkatesan Guruswami

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 ε/log O(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.

SODA Conference 2004 Conference Paper

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates

• Venkatesan Guruswami
• Piotr Indyk

STOC Conference 2003 Conference Paper

A new multilayered PCP and the hardness of hypergraph vertex cover

• Irit Dinur
• Venkatesan Guruswami
• Subhash Khot
• Oded Regev 0001

Given a k -uniform hyper-graph, the E k -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 E k -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.

FOCS Conference 2003 Conference Paper

Clustering with Qualitative Information

• Moses Charikar
• Venkatesan Guruswami
• Anthony Wirth

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.

SODA Conference 2003 Conference Paper

Embeddings and non-approximability of geometric problems

• Venkatesan Guruswami
• Piotr Indyk

STOC Conference 2003 Conference Paper

Linear time encodable and list decodable codes

• Venkatesan Guruswami
• Piotr Indyk

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.

SODA Conference 2003 Conference Paper

Unconditional proof of tightness of Johnson bound

• Venkatesan Guruswami
• Igor E. Shparlinski

SODA Conference 2002 Conference Paper

Guessing secrets efficiently via list decoding

• Noga Alon
• Venkatesan Guruswami
• Tali Kaufman
• Madhu Sudan 0001

STOC Conference 2002 Conference Paper

Limits to list decodability of linear codes

• Venkatesan Guruswami

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.

STOC Conference 2002 Conference Paper

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets

• Venkatesan Guruswami
• Piotr Indyk

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 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.

FOCS Conference 2001 Conference Paper

Expander-Based Constructions of Efficiently Decodable Codes

• Venkatesan Guruswami
• Piotr Indyk

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.

FOCS Conference 2000 Conference Paper

"Soft-decision" Decoding of Chinese Remainder Codes

• Venkatesan Guruswami
• Amit Sahai
• Madhu Sudan 0001

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.

FOCS Conference 2000 Conference Paper

Combinatorial feature selection problems

• Moses Charikar
• Venkatesan Guruswami
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai

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.

FOCS Conference 2000 Conference Paper

Hardness of Approximate Hypergraph Coloring

• Venkatesan Guruswami
• Johan Håstad
• Madhu Sudan 0001

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.

STOC Conference 2000 Conference Paper

List decoding algorithms for certain concatenated codes

• Venkatesan Guruswami
• Madhu Sudan 0001

STOC Conference 2000 Conference Paper

Query strategies for priced information (extended abstract)

• Moses Charikar
• Ronald Fagin
• Venkatesan Guruswami
• Jon M. Kleinberg
• Prabhakar Raghavan
• Amit Sahai

STOC Conference 1999 Conference Paper

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems

• Venkatesan Guruswami
• Sanjeev Khanna
• Rajmohan Rajaraman
• F. Bruce Shepherd
• Mihalis Yannakakis

SODA Conference 1999 Conference Paper

The 2-Catalog Segmentation Problem

• Yevgeniy Dodis
• Venkatesan Guruswami
• Sanjeev Khanna

FOCS Conference 1998 Conference Paper

A Tight Characterization of NP with 3 Query PCPs

• Venkatesan Guruswami
• Daniel Lewin 0001
• Madhu Sudan 0001
• Luca Trevisan 0001

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.

FOCS Conference 1998 Conference Paper

Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes

• Venkatesan Guruswami
• Madhu Sudan 0001

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 e 1/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.