All reports by Author Venkatesan Guruswami:

__
TR17-080
| 1st May 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### The Quest for Strong Inapproximability Results with Perfect Completeness

__
TR17-064
| 20th April 2017
__

Venkatesan Guruswami, Chaoping Xing, chen yuan#### Subspace Designs based on Algebraic Function Fields

__
TR16-185
| 18th November 2016
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

__
TR16-183
| 16th November 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 1

__
TR16-033
| 10th March 2016
__

Venkatesan Guruswami, Jaikumar Radhakrishnan#### Tight bounds for communication assisted agreement distillation

__
TR16-029
| 7th March 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### New hardness results for graph and hypergraph colorings

__
TR15-155
| 22nd September 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Nearly Optimal NP-Hardness of Unique Coverage

__
TR15-117
| 21st July 2015
__

Boris Bukh, Venkatesan Guruswami#### An improved bound on the fraction of correctable deletions

Revisions: 1

__
TR15-116
| 21st July 2015
__

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky#### Efficient Low-Redundancy Codes for Correcting Multiple Deletions

__
TR15-105
| 21st June 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Towards a Characterization of Approximation Resistance for Symmetric CSPs

__
TR14-165
| 3rd December 2014
__

Venkatesan Guruswami, Ameya Velingker#### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

__
TR14-162
| 28th November 2014
__

Michael Forbes, Venkatesan Guruswami#### Dimension Expanders via Rank Condensers

__
TR14-153
| 14th November 2014
__

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan#### Communication with Imperfectly Shared Randomness

Revisions: 2

__
TR14-067
| 4th May 2014
__

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

__
TR14-043
| 2nd April 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

__
TR14-006
| 16th January 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Inapproximability of Feedback Vertex Set for Bounded Length Cycles

Revisions: 1

__
TR13-175
| 6th December 2013
__

Venkatesan Guruswami, Chaoping Xing#### Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

__
TR13-170
| 2nd December 2013
__

Venkatesan Guruswami, Carol Wang#### Explicit rank-metric codes list-decodable with optimal redundancy

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan Håstad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

__
TR13-125
| 11th September 2013
__

Venkatesan Guruswami, Euiwoong Lee#### Complexity of approximating CSP with Balance / Hard Constraints

__
TR13-122
| 5th September 2013
__

Irit Dinur, Venkatesan Guruswami#### PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

__
TR13-121
| 4th September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Non-Malleable Coding Against Bit-wise and Split-State Tampering

Revisions: 1

__
TR13-118
| 2nd September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Capacity of Non-Malleable Codes

__
TR13-071
| 8th May 2013
__

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket#### Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

__
TR13-050
| 1st April 2013
__

Venkatesan Guruswami, Patrick Xia#### Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

__
TR13-046
| 27th March 2013
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

__
TR13-002
| 31st December 2012
__

Venkatesan Guruswami, Krzysztof Onak#### Superlinear lower bounds for multipass graph processing

Revisions: 3

__
TR12-146
| 7th November 2012
__

Venkatesan Guruswami, Chaoping Xing#### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

__
TR12-111
| 5th September 2012
__

Venkatesan Guruswami, Ali Kemal Sinop#### Faster SDP hierarchy solvers for local rounding algorithms

__
TR12-082
| 28th June 2012
__

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker#### Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

__
TR12-074
| 12th June 2012
__

Venkatesan Guruswami, Yuan Zhou#### Approximating Bounded Occurrence Ordering CSPs

__
TR12-073
| 11th June 2012
__

Venkatesan Guruswami, Carol Wang#### Linear-algebraic list decoding for variants of Reed-Solomon codes

__
TR12-036
| 12th April 2012
__

Venkatesan Guruswami, Chaoping Xing#### Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

__
TR12-017
| 1st March 2012
__

Venkatesan Guruswami, Srivatsan Narayanan#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

__
TR11-066
| 25th April 2011
__

Venkatesan Guruswami, Ali Kemal Sinop#### Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR10-185
| 2nd December 2010
__

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu#### Agnostic Learning of Monomials by Halfspaces is Hard

__
TR10-177
| 16th November 2010
__

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu#### Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

__
TR10-111
| 14th July 2010
__

Venkatesan Guruswami, Ali Kemal Sinop#### The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

__
TR10-077
| 26th April 2010
__

Venkatesan Guruswami, Adam Smith#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

__
TR10-063
| 12th April 2010
__

Venkatesan Guruswami, Yuan Zhou#### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Hastad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR09-126
| 26th November 2009
__

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman#### Locally Testable Codes Require Redundant Testers

Revisions: 3

__
TR09-099
| 16th October 2009
__

Venkatesan Guruswami, Ali Kemal Sinop#### Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

__
TR09-020
| 2nd March 2009
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

__
TR09-001
| 26th November 2008
__

Venkatesan Guruswami#### Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR08-054
| 13th May 2008
__

Venkatesan Guruswami, Atri Rudra#### Concatenated codes can achieve list-decoding capacity

__
TR08-036
| 14th March 2008
__

Venkatesan Guruswami, Atri Rudra#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

__
TR08-008
| 8th February 2008
__

Venkatesan Guruswami, Prasad Raghavendra#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

__
TR07-113
| 15th November 2007
__

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang#### Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

__
TR07-109
| 7th October 2007
__

Venkatesan Guruswami, Atri Rudra#### Better Binary List-Decodable Codes via Multilevel Concatenation

__
TR07-089
| 13th September 2007
__

Parikshit Gopalan, Venkatesan Guruswami#### Deterministic Hardness Amplification via Local GMD Decoding

__
TR07-086
| 7th September 2007
__

Venkatesan Guruswami, James R. Lee, Alexander Razborov#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

__
TR06-141
| 22nd November 2006
__

Venkatesan Guruswami, Kunal Talwar#### Hardness of Low Congestion Routing in Directed Graphs

__
TR06-134
| 18th October 2006
__

Venkatesan Guruswami, Chris Umans, Salil Vadhan#### Extractors and condensers from univariate polynomials

Revisions: 1

__
TR06-123
| 15th September 2006
__

Venkatesan Guruswami, Venkatesan Guruswami#### Iterative Decoding of Low-Density Parity Check Codes (A Survey)

__
TR06-123
| 15th September 2006
__

Venkatesan Guruswami, Venkatesan Guruswami#### Iterative Decoding of Low-Density Parity Check Codes (A Survey)

__
TR06-061
| 5th May 2006
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Learning Halfspaces with Noise

__
TR05-133
| 17th November 2005
__

Venkatesan Guruswami, Atri Rudra#### Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

__
TR05-132
| 8th November 2005
__

Venkatesan Guruswami#### Algebraic-geometric generalizations of the Parvaresh-Vardy codes

__
TR05-057
| 19th May 2005
__

Venkatesan Guruswami, Valentine Kabanets#### Hardness amplification via space-efficient direct products

__
TR05-019
| 9th February 2005
__

Venkatesan Guruswami, Atri Rudra#### Tolerant Locally Testable Codes

__
TR04-040
| 4th May 2004
__

Venkatesan Guruswami, Alexander Vardy#### Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

__
TR03-080
| 12th November 2003
__

Venkatesan Guruswami#### Better Extractors for Better Codes?

__
TR02-053
| 20th July 2002
__

Lars Engebretsen, Venkatesan Guruswami#### Is Constraint Satisfaction Over Two Variables Always Easy?

__
TR02-027
| 30th April 2002
__

Irit Dinur, Venkatesan Guruswami, Subhash Khot#### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

__
TR01-002
| 6th December 2000
__

Venkatesan Guruswami#### Constructions of Codes from Number Fields

__
TR00-073
| 28th August 2000
__

Venkatesan Guruswami, Sanjeev Khanna#### On the Hardness of 4-coloring a 3-colorable Graph

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Hastad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR99-043
| 5th November 1999
__

Venkatesan Guruswami#### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

__
TR98-043
| 27th July 1998
__

Venkatesan Guruswami, Madhu Sudan#### Improved decoding of Reed-Solomon and algebraic-geometric codes.

__
TR98-034
| 23rd June 1998
__

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan#### A tight characterization of NP with 3 query PCPs

Joshua Brakensiek, Venkatesan Guruswami

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

Venkatesan Guruswami, Chaoping Xing, chen yuan

Subspace designs are a (large) collection of high-dimensional subspaces $\{H_i\}$ of $\F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $W \cap H_i$ is at most some parameter $L$. The ... more >>>

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 \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>>

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

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 $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

Venkatesan Guruswami, Euiwoong Lee

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to $1$ with some probability $\alpha$ achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>>

Venkatesan Guruswami, Ameya Velingker

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

Michael Forbes, Venkatesan Guruswami

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

Venkatesan Guruswami, Euiwoong Lee

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation ... more >>>

Venkatesan Guruswami, Chaoping Xing

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

Venkatesan Guruswami, Carol Wang

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, 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.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Per Austrin, Venkatesan Guruswami, Johan Håstad

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

Venkatesan Guruswami, Euiwoong Lee

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

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

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs ($k=2$), the minimum vertex cover can be computed in polynomial time. For $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was ... more >>>

Venkatesan Guruswami, Swastik Kopparty

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

Venkatesan Guruswami, Patrick Xia

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to ``fold" the AG code. ... more >>>

Venkatesan Guruswami, Krzysztof Onak

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

Venkatesan Guruswami, Chaoping Xing

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

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 {\em rounds} $r$ in the hierarchy, though the complexity of solving

(or even writing down the solution for) ...
more >>>

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker

We prove that a random linear code over $\mathbb{F}_q$, with probability arbitrarily close to $1$, is list decodable at radius $1-1/q-\epsilon$ with list size $L=O(1/\epsilon^2)$ and rate $R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in $1/\epsilon$ and constant factors depending on $q$, this matches the lower bound $L=\Omega_q(1/\epsilon^2)$ for the list ... more >>>

Venkatesan Guruswami, Yuan Zhou

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>

Venkatesan Guruswami, Carol Wang

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any $\epsilon > 0$, Guruswami and Rudra presented an $n^{O(1/\epsilon)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\epsilon$ of ... more >>>

Venkatesan Guruswami, Chaoping Xing

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

Venkatesan Guruswami, Srivatsan Narayanan

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear 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 ... more >>>

Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good

coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and

$n$ is the number of vertices):

Venkatesan Guruswami, Adam Smith

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

Venkatesan Guruswami, Yuan Zhou

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 {\em

near-satisfiable} instance.

\begin{enumerate}

\item ...
more >>>

Venkatesan Guruswami, Johan Hastad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

Venkatesan Guruswami, Prasad Raghavendra

A classic result due to Hastad established that for every constant \eps > 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-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

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 conducive to list

decoding arise out of the Artin-Frobenius automorphism at primes ...
more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, 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 ... more >>>

Venkatesan Guruswami, Atri Rudra

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

Venkatesan Guruswami, Atri Rudra

We construct binary linear codes that are efficiently list-decodable

up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits

into $n = {\rm poly}(k/\eps)$ bits and are constructible and

list-decodable in time polynomial in $k$ and $1/\eps$ (in

particular, in our results $\eps$ need ...
more >>>

Venkatesan Guruswami, Prasad Raghavendra

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed ...
more >>>

Venkatesan Guruswami, Atri Rudra

We give a polynomial time construction of binary codes with the best

currently known trade-off between rate and error-correction

radius. Specifically, we obtain linear codes over fixed alphabets

that can be list decoded in polynomial time up to the so called

Blokh-Zyablov bound. Our work ...
more >>>

Parikshit Gopalan, Venkatesan Guruswami

We study the average-case hardness of the class NP against

deterministic polynomial time algorithms. We prove that there exists

some constant $\mu > 0$ such that if there is some language in NP

for which no deterministic polynomial time algorithm can decide L

correctly on a $1- (log n)^{-\mu}$ fraction ...
more >>>

Venkatesan Guruswami, James R. Lee, Alexander Razborov

We give an explicit (in particular, deterministic polynomial time)

construction of subspaces $X

\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,

$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$

If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits

and ...
more >>>

Venkatesan Guruswami, Kunal Talwar

We prove a strong inapproximability result for routing on directed

graphs with low congestion. Given as input a directed graph on $N$

vertices and a set of source-destination pairs that can be connected

via edge-disjoint paths, we prove that it is hard, assuming NP

doesn't have $n^{O(\log\log n)}$ time randomized ...
more >>>

Venkatesan Guruswami, Chris Umans, Salil Vadhan

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

Venkatesan Guruswami, Venkatesan Guruswami

Much progress has been made on decoding algorithms for

error-correcting codes in the last decade. In this article, we give an

introduction to some fundamental results on iterative, message-passing

algorithms for low-density parity check codes. For certain

important stochastic channels, this line of work has enabled getting

very close to ...
more >>>

Venkatesan Guruswami, Venkatesan Guruswami

error-correcting codes in the last decade. In this article, we give an

introduction to some fundamental results on iterative, message-passing

algorithms for low-density parity check codes. For certain

important stochastic channels, this line of work has enabled getting

very close to ...
more >>>

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 halfspace consistent with all the

training examples exists, the problem can be solved in polynomial

time using linear programming. ...
more >>>

Venkatesan Guruswami, Atri Rudra

For every $0 < R < 1$ and $\eps > 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-\eps)$ of errors.

These codes achieve the ``capacity'' for decoding from {\em ...
more >>>

Venkatesan Guruswami

This paper is concerned with a new family of error-correcting codes

based on algebraic curves over finite fields, and list decoding

algorithms for them. The basic goal in the subject of list decoding is

to construct error-correcting codes $C$ over some alphabet $\Sigma$

which have good rate $R$, and at ...
more >>>

Venkatesan Guruswami, Valentine Kabanets

We prove a version of the derandomized Direct Product Lemma for

deterministic space-bounded algorithms. Suppose a Boolean function

$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$

fraction of inputs by any deterministic time $T$ and space $S$

algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step

walks $w=(v_1,\dots, v_t)$ ...
more >>>

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>

Venkatesan Guruswami, Alexander Vardy

Maximum-likelihood decoding is one of the central algorithmic

problems in coding theory. It has been known for over 25 years

that maximum-likelihood decoding of general linear codes is

NP-hard. Nevertheless, it was so far unknown whether maximum-

likelihood decoding remains hard for any specific family of

more >>>

Venkatesan Guruswami

We present an explicit construction of codes that can be list decoded

from a fraction $(1-\eps)$ of errors in sub-exponential time and which

have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal

rate of $\Omega(\eps)$, and is the first sub-exponential complexity

construction to beat the rate of $O(\eps^2)$ achieved by ...
more >>>

Lars Engebretsen, Venkatesan Guruswami

By the breakthrough work of Håstad, several constraint satisfaction

problems are now known to have the following approximation resistance

property: satisfying more clauses than what picking a random

assignment would achieve is NP-hard. This is the case for example for

Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ...
more >>>

Irit Dinur, Venkatesan Guruswami, Subhash Khot

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is

to find a minimum subset of vertices that ``hits'' every edge. We

show that for every integer $k \geq 5$, E$k$-Vertex-Cover is

NP-hard to approximate within a factor of $(k-3-\epsilon)$, for

an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

Venkatesan Guruswami

We define number-theoretic error-correcting codes based on algebraic

number fields, thereby providing a generalization of Chinese Remainder

Codes akin to the generalization of Reed-Solomon codes to

Algebraic-geometric codes. Our construction is very similar to

(and in fact less general than) the one given by (Lenstra 1986), but

the ...
more >>>

Venkatesan Guruswami, Sanjeev Khanna

We give a new proof showing that it is NP-hard to color a 3-colorable

graph using just four colors. This result is already known (Khanna,

Linial, Safra 1992), but our proof is novel as it does not rely on

the PCP theorem, while the earlier one does. This ...
more >>>

Venkatesan Guruswami, Johan Hastad, Madhu Sudan

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

Venkatesan Guruswami

We prove hardness results for approximating set splitting problems and

also instances of satisfiability problems which have no ``mixed'' clauses,

i.e all clauses have either all their literals unnegated or all of them

negated. Recent results of Hastad imply tight hardness results for set

splitting when all sets ...
more >>>

Venkatesan Guruswami, Madhu Sudan

We present an improved list decoding algorithm for decoding

Reed-Solomon codes. Given an arbitrary string of length n, the

list decoding problem is that of finding all codewords within a

specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon

codes reduces to the ...
more >>>

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

It is known that there exists a PCP characterization of NP

where the verifier makes 3 queries and has a {\em 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 ...
more >>>