# Venkatesan Guruswami

According to our database1, Venkatesan Guruswami authored at least 369 papers between 1998 and 2018.

Collaborative distances :
• Dijkstra number2 of three.
• Erdős number3 of two.

## ACM Fellow

ACM Fellow 2017, "For contributions to algorithmic coding theory, pseudorandomness and the complexity of approximate optimization".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
IEEE Trans. Information Theory, 2018

Lossless dimension expanders via linearized polynomials and subspace designs.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Beating Fredman-Komlós for perfect $k$-hashing.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Combining LPs and Ring Equations via Structured Polymorphisms.
Electronic Colloquium on Computational Complexity (ECCC), 2018

General Strong Polarization.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Approximating Operator Norms via Generalized Krivine Rounding.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Inapproximability of Matrix $p \rightarrow q$ Norms.
Electronic Colloquium on Computational Complexity (ECCC), 2018

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.
CoRR, 2018

ε-MSR Codes: Contacting Fewer Code Blocks for Exact Repair.
CoRR, 2018

How long can optimal locally repairable codes be?
CoRR, 2018

Beating Fredman-Komlós for perfect k-hashing.
CoRR, 2018

Approximating Operator Norms via Generalized Krivine Rounding.
CoRR, 2018

Inapproximability of Matrix p→q Norms.
CoRR, 2018

General Strong Polarization.
CoRR, 2018

General strong polarization.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Coding against deletions in oblivious and online models.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs.
Proceedings of the 33rd Computational Complexity Conference, 2018

How Long Can Optimal Locally Repairable Codes Be?.
Proceedings of the Approximation, 2018

Polar Codes with Exponentially Small Error at Finite Block Length.
Proceedings of the Approximation, 2018

2017
Towards a Characterization of Approximation Resistance for Symmetric CSPs.
Theory of Computing, 2017

Repairing Reed-Solomon Codes.
IEEE Trans. Information Theory, 2017

Deletion Codes in the High-Noise and High-Rate Regimes.
IEEE Trans. Information Theory, 2017

Efficiently List-Decodable Punctured Reed-Muller Codes.
IEEE Trans. Information Theory, 2017

Communication With Imperfectly Shared Randomness.
IEEE Trans. Information Theory, 2017

An Improved Bound on the Fraction of Correctable Deletions.
IEEE Trans. Information Theory, 2017

Inapproximability of H-Transversal/Packing.
SIAM J. Discrete Math., 2017

Nearly Optimal NP-Hardness of Unique Coverage.
SIAM J. Comput., 2017

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.
SIAM J. Comput., 2017

(2+ε)-Sat Is NP-hard.
SIAM J. Comput., 2017

Non-malleable Coding Against Bit-Wise and Split-State Tampering.
J. Cryptology, 2017

Subspace Designs based on Algebraic Function Fields.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Hardness of Rainbow Coloring Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2017

On Maximally Recoverable Local Reconstruction Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover.
Electronic Colloquium on Computational Complexity (ECCC), 2017

The Quest for Strong Inapproximability Results with Perfect Completeness.
Electronic Colloquium on Computational Complexity (ECCC), 2017

On the List-Decodability of Random Linear Rank-Metric Codes.
CoRR, 2017

On Maximally Recoverable Local Reconstruction Codes.
CoRR, 2017

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth.
CoRR, 2017

Optimal rate list decoding over bounded alphabets using algebraic-geometric codes.
CoRR, 2017

Subspace Designs based on Algebraic Function Fields.
CoRR, 2017

Efficiently decodable codes for the binary deletion channel.
CoRR, 2017

Locality via Partially Lifted Codes.
CoRR, 2017

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.
CoRR, 2017

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

∊-MSR codes with small sub-packetization.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

An improved bound on the zero-error list-decoding capacity of the 4/3 channel.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Subspace Designs Based on Algebraic Function Fields.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Hardness of Rainbow Coloring Hypergraphs.
Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.
Proceedings of the Approximation, 2017

Efficiently Decodable Codes for the Binary Deletion Channel.
Proceedings of the Approximation, 2017

Locality via Partially Lifted Codes.
Proceedings of the Approximation, 2017

The Quest for Strong Inapproximability Results with Perfect Completeness.
Proceedings of the Approximation, 2017

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere.
Proceedings of the Approximation, 2017

2016
Decoding Reed-Solomon Codes.
Encyclopedia of Algorithms, 2016

Simple Proof of Hardness of Feedback Vertex Set.
Theory of Computing, 2016

Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs.
IEEE Trans. Information Theory, 2016

Capacity of Non-Malleable Codes.
IEEE Trans. Information Theory, 2016

Bypassing UGC from Some Optimal Geometric Inapproximability Results.
ACM Trans. Algorithms, 2016

Complexity of Approximating CSP with Balance / Hard Constraints.
Theory Comput. Syst., 2016

Optimal Rate Code Constructions for Computationally Simple Channels.
J. ACM, 2016

Tight bounds for communication assisted agreement distillation.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.
Electronic Colloquium on Computational Complexity (ECCC), 2016

New hardness results for graph and hypergraph colorings.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.
Electronic Colloquium on Computational Complexity (ECCC), 2016

New MDS codes with small sub-packetization and near-optimal repair bandwidth.
CoRR, 2016

Codes correcting deletions in oblivious and random models.
CoRR, 2016

Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes.
CoRR, 2016

Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey).
CoRR, 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.
CoRR, 2016

Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy.
CoRR, 2016

Explicit subspace designs.
Combinatorica, 2016

Superlinear Lower Bounds for Multipass Graph Processing.
Algorithmica, 2016

Repairing Reed-solomon codes.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Nearly Optimal NP-Hardness of Unique Coverage.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

An improved bound on the fraction of correctable deletions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes.
Proceedings of the IEEE International Symposium on Information Theory, 2016

Robust Fourier and Polynomial Curve Fitting.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Tight Bounds for Communication-Assisted Agreement Distillation.
Proceedings of the 31st Conference on Computational Complexity, 2016

New Hardness Results for Graph and Hypergraph Colorings.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity.
IEEE Trans. Information Theory, 2015

Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs.
SIAM J. Discrete Math., 2015

Optimal rate algebraic list decoding using narrow ray class fields.
J. Comb. Theory, Ser. A, 2015

Nearly Optimal NP-Hardness of Unique Coverage.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Towards a Characterization of Approximation Resistance for Symmetric CSPs.
Electronic Colloquium on Computational Complexity (ECCC), 2015

An improved bound on the fraction of correctable deletions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).
Dagstuhl Reports, 2015

Repairing Reed-Solomon Codes.
CoRR, 2015

Inapproximability of $H$-Transversal/Packing.
CoRR, 2015

Efficient list decoding of punctured Reed-Muller codes.
CoRR, 2015

An improved bound on the fraction of correctable deletions.
CoRR, 2015

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
CoRR, 2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises.
CoRR, 2015

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Communication with Imperfectly Shared Randomness.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets.
Proceedings of the 30th Conference on Computational Complexity, 2015

Deletion Codes in the High-noise and High-rate Regimes.
Proceedings of the Approximation, 2015

Towards a Characterization of Approximation Resistance for Symmetric CSPs.
Proceedings of the Approximation, 2015

Inapproximability of H-Transversal/Packing.
Proceedings of the Approximation, 2015

Dimension Expanders via Rank Condensers.
Proceedings of the Approximation, 2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises.
Proceedings of the Approximation, 2015

2014
IEEE Trans. Information Theory, 2014

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems.
SIAM Journal on Optimization, 2014

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Inapproximability of Feedback Vertex Set for Bounded Length Cycles.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Dimension Expanders via Rank Condensers.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Communication with Imperfectly Shared Randomness.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Deletion codes in the high-noise and high-rate regimes.
CoRR, 2014

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets.
CoRR, 2014

Dimension Expanders via Rank Condensers.
CoRR, 2014

Communication with Imperfectly Shared Randomness.
CoRR, 2014

Non-malleable Coding against Bit-Wise and Split-State Tampering.
Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
Proceedings of the Symposium on Theory of Computing, 2014

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Complexity of approximating CSP with balance / hard constraints.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Capacity of non-malleable codes.
Proceedings of the Innovations in Theoretical Computer Science, 2014

(2 + epsilon)-Sat Is NP-Hard.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Hitting Sets for Low-Degree Polynomials with Optimal Density.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes.
Proceedings of the Approximation, 2014

2013
Improved Inapproximability Results for Maximum k-Colorable Subgraph.
Theory of Computing, 2013

Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes.
IEEE Trans. Information Theory, 2013

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
SIAM J. Comput., 2013

Non-Malleable Coding Against Bit-wise and Split-State Tampering.
IACR Cryptology ePrint Archive, 2013

Capacity of Non-Malleable Codes.
IACR Cryptology ePrint Archive, 2013

Hitting Sets for Low-Degree Polynomials with Optimal Density.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Polar Codes: Speed of polarization and polynomial gap to capacity.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Explicit rank-metric codes list-decodable with optimal redundancy.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Superlinear lower bounds for multipass graph processing.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Complexity of approximating CSP with Balance / Hard Constraints.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Explicit Subspace Designs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
Electronic Colloquium on Computational Complexity (ECCC), 2013

PCPs via low-degree long code and hardness for constrained hypergraph coloring.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Non-Malleable Coding Against Bit-wise and Split-State Tampering.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Capacity of Non-Malleable Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2013

(2+ε)-SAT is NP-hard.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Polar Codes: Speed of polarization and polynomial gap to capacity
CoRR, 2013

Optimal rate algebraic list decoding using narrow ray class fields
CoRR, 2013

Explicit rank-metric codes list-decodable with optimal redundancy.
CoRR, 2013

Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs.
CoRR, 2013

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
CoRR, 2013

Non-Malleable Coding Against Bit-wise and Split-State Tampering.
CoRR, 2013

Capacity of Non-Malleable Codes.
CoRR, 2013

CopyCatch: stopping group attacks by spotting lockstep behavior in social networks.
Proceedings of the 22nd International World Wide Web Conference, 2013

List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Approximating Non-Uniform Sparsest Cut Via Generalized Spectra.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Polar Codes: Speed of Polarization and Polynomial Gap to Capacity.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Explicit Subspace Designs.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Superlinear Lower Bounds for Multipass Graph Processing.
Proceedings of the 28th Conference on Computational Complexity, 2013

Combinatorial Limitations of Average-Radius List Decoding.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set.
Theory of Computing, 2012

Agnostic Learning of Monomials by Halfspaces Is Hard.
SIAM J. Comput., 2012

Approximating Bounded Occurrence Ordering CSPs.
Electronic Colloquium on Computational Complexity (ECCC), 2012

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Linear-algebraic list decoding for variants of Reed-Solomon codes.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Faster SDP hierarchy solvers for local rounding algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Combinatorial limitations of a strong form of list decoding.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Superlinear lower bounds for multipass graph processing
CoRR, 2012

Faster SDP hierarchy solvers for local rounding algorithms
CoRR, 2012

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
CoRR, 2012

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding
CoRR, 2012

Combinatorial limitations of a strong form of list decoding
CoRR, 2012

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
CoRR, 2012

List decoding subspace codes from insertions and deletions
CoRR, 2012

Folded codes from function field towers and improved optimal rate list decoding.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Optimal column-based low-rank matrix reconstruction.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Bypassing UGC from some optimal geometric inapproximability results.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

List decoding subspace codes from insertions and deletions.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Faster SDP Hierarchy Solvers for Local Rounding Algorithms.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Approximating Bounded Occurrence Ordering CSPs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes.
IEEE Trans. Information Theory, 2011

On the List-Decodability of Random Linear Codes.
IEEE Trans. Information Theory, 2011

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.
SIAM J. Comput., 2011

List Decoding Tensor Products and Interleaved Codes.
SIAM J. Comput., 2011

Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008).
SIAM J. Comput., 2011

Hardness amplification within NP against deterministic algorithms.
J. Comput. Syst. Sci., 2011

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra
CoRR, 2011

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

Optimal rate list decoding via derivative codes
CoRR, 2011

Linear-algebraic list decoding of folded Reed-Solomon codes
CoRR, 2011

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
CoRR, 2011

Optimal Column-Based Low-Rank Matrix Reconstruction
CoRR, 2011

The query complexity of estimating weighted averages.
Acta Inf., 2011

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Finding Almost-Perfect Graph Bisections.
Proceedings of the Innovations in Computer Science, 2011

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Linear-Algebraic List Decoding of Folded Reed-Solomon Codes.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Optimal Rate List Decoding via Derivative Codes.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
A Lower Bound on List Size for List Decoding.
IEEE Trans. Information Theory, 2010

The existence of concatenated codes list-decodable up to the hamming bound.
IEEE Trans. Information Theory, 2010

Locally Testable Codes Require Redundant Testers.
SIAM J. Comput., 2010

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}.
Electronic Colloquium on Computational Complexity (ECCC), 2010

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Bypassing UGC from some optimal geometric inapproximability results.
Electronic Colloquium on Computational Complexity (ECCC), 2010

On the List-Decodability of Random Linear Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Agnostic Learning of Monomials by Halfspaces is Hard.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Agnostic Learning of Monomials by Halfspaces is Hard
CoRR, 2010

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
CoRR, 2010

On the List-Decodability of Random Linear Codes
CoRR, 2010

Almost Euclidean subspaces of l 1N VIA expander codes.
Combinatorica, 2010

Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.
Combinatorica, 2010

On the list-decodability of random linear codes.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.
TOCT, 2009

Better Binary List Decodable Codes Via Multilevel Concatenation.
IEEE Trans. Information Theory, 2009

Hardness of Learning Halfspaces with Noise.
SIAM J. Comput., 2009

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.
J. ACM, 2009

Improved Inapproximability Results for Maximum k-Colorable Subgraph.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Locally Testable Codes Require Redundant Testers.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Improved Inapproximability Results for Maximum k-Colorable Subgraph
CoRR, 2009

Error correction up to the information-theoretic limit.
Commun. ACM, 2009

Artin automorphisms, cyclotomic function fields, and folded list-decodable codes.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

List decoding tensor products and interleaved codes.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

MaxMin allocation via degree lower-bounded arborescences.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Agnostic Learning of Monomials by Halfspaces Is Hard.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

List Decoding of Binary Codes-A Brief Survey of Some Recent Results.
Proceedings of the Coding and Cryptology, Second International Workshop, 2009

Every Permutation CSP of arity 3 is Approximation Resistant.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Locally Testable Codes Require Redundant Testers.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Improved Inapproximability Results for Maximum k-Colorable Subgraph.
Proceedings of the Approximation, 2009

2008
Decoding Reed-Solomon Codes.
Proceedings of the Encyclopedia of Algorithms, 2008

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.
IEEE Trans. Information Theory, 2008

Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets.
Math. Comput., 2008

Concatenated codes can achieve list-decoding capacity.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.
Electronic Colloquium on Computational Complexity (ECCC), 2008

List Decoding Tensor Products and Interleaved Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2008

List Decoding Tensor Products and Interleaved Codes
CoRR, 2008

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
CoRR, 2008

Hardness Amplification via Space-Efficient Direct Products.
Computational Complexity, 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica, 2008

Concatenated codes can achieve list-decoding capacity.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Almost Euclidean subspaces of lN1 via expander codes.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

List Error-Correction with Optimal Information Rate (Invited Talk).
Proceedings of the Information Theoretic Security, Third International Conference, 2008

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Hardness Amplification within NP against Deterministic Algorithms.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.
Proceedings of the Approximation, 2008

Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
Proceedings of the Approximation, 2008

2007
Guessing secrets efficiently via list decoding.
ACM Trans. Algorithms, 2007

Better Binary List-Decodable Codes via Multilevel Concatenation.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Almost Euclidean subspaces of ℓ1N via expander codes.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Deterministic Hardness Amplification via Local GMD Decoding.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Computational Complexity, 2007

A 3-query PCP over integers.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Hardness of routing with congestion in directed graphs.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

Better Binary List-Decodable Codes Via Multilevel Concatenation.
Proceedings of the Approximation, 2007

List Decoding and Pseudorandom Constructions.
Proceedings of the Applied Algebra, 2007

2006
Correlation Clustering with a Fixed Number of Clusters.
Theory of Computing, 2006

Limits to List Decoding Reed-Solomon Codes.
IEEE Trans. Information Theory, 2006

Algorithmic Results in List Decoding.
Foundations and Trends in Theoretical Computer Science, 2006

Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Hardness of Low Congestion Routing in Directed Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Hardness of Learning Halfspaces with Noise.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Iterative Decoding of Low-Density Parity Check Codes (A Survey).
Electronic Colloquium on Computational Complexity (ECCC), 2006

Iterative Decoding of Low-Density Parity Check Codes.
Bulletin of the EATCS, 2006

Iterative Decoding of Low-Density Parity Check Codes (A Survey)
CoRR, 2006

Explicit capacity-achieving list-decodable codes.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Correlation clustering with a fixed number of clusters.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Hardness Amplification Via Space-Efficient Direct Products.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

On 2-Query Codeword Testing with Near-Perfect Completeness.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Hardness of Learning Halfspaces with Noise.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
IEEE Trans. Information Theory, 2005

Linear-time encodable/decodable codes with near-optimal rate.
IEEE Trans. Information Theory, 2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput., 2005

Clustering with qualitative information.
J. Comput. Syst. Sci., 2005

Explicit Capacity-Achieving List-Decodable Codes
Electronic Colloquium on Computational Complexity (ECCC), 2005

Algebraic-geometric generalizations of the Parvaresh-Vardy codes
Electronic Colloquium on Computational Complexity (ECCC), 2005

Hardness amplification via space-efficient direct products
Electronic Colloquium on Computational Complexity (ECCC), 2005

Tolerant Locally Testable Codes
Electronic Colloquium on Computational Complexity (ECCC), 2005

Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
CoRR, 2005

Correlation Clustering with a Fixed Number of Clusters
CoRR, 2005

The complexity of the covering radius problem.
Computational Complexity, 2005

Limits to list decoding Reed-Solomon codes.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On profit-maximizing envy-free pricing.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Hardness of Max 3SAT with No Mixed Clauses.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

A Lower Bound on List Size for List Decoding.
Proceedings of the Approximation, 2005

The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
Proceedings of the Approximation, 2005

Tolerant Locally Testable Codes.
Proceedings of the Approximation, 2005

2004
Guest column: error-correcting codes and expander graphs.
SIGACT News, 2004

On the Hardness of 4-Coloring a 3-Colorable Graph.
SIAM J. Discrete Math., 2004

Is constraint satisfaction over two variables always easy?
Random Struct. Algorithms, 2004

Guest Editors' foreword.
J. Comput. Syst. Sci., 2004

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
Electronic Colloquium on Computational Complexity (ECCC), 2004

Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
CoRR, 2004

Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
Algorithmica, 2004

Better extractors for better codes?
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

The Complexity of the Covering Radius Problem on Lattices and Codes.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition)
Lecture Notes in Computer Science 3282, Springer, ISBN: 3-540-24051-9, 2004

2003
List decoding from erasures: bounds and code constructions.
IEEE Trans. Information Theory, 2003

Constructions of codes from number fields.
IEEE Trans. Information Theory, 2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.
J. Comput. Syst. Sci., 2003

Better Extractors for Better Codes?
Electronic Colloquium on Computational Complexity (ECCC), 2003

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
CoRR, 2003

Linear time encodable and list decodable codes.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A new multilayered PCP and the hardness of hypergraph vertex cover.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Unconditional proof of tightness of Johnson bound.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embeddings and non-approximability of geometric problems.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Clustering with Qualitative Information.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

List Decoding with Side Information.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Combinatorial bounds for list decoding.
IEEE Trans. Information Theory, 2002

Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput., 2002

Query Strategies for Priced Information.
J. Comput. Syst. Sci., 2002

Is Constraint Satisfaction Over Two Variables Always Easy?
Electronic Colloquium on Computational Complexity (ECCC), 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electronic Colloquium on Computational Complexity (ECCC), 2002

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Limits to list decodability of linear codes.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Guessing secrets efficiently via list decoding.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Is Constraint Satisfaction Over Two Variables Always Easy?
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Decoding Concatenated Codes using Soft Information.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
List decoding of error correcting codes.
PhD thesis, 2001

On representations of algebraic-geometry codes.
IEEE Trans. Information Theory, 2001

Constructions of Codes from Number Fields
Electronic Colloquium on Computational Complexity (ECCC), 2001

The Kr-Packing Problem.
Computing, 2001

List Decoding from Erasures: Bounds and Code Constructions.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Expander-Based Constructions of Efficiently Decodable Codes.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Constructions of Codes from Number Fields.
Proceedings of the Applied Algebra, 2001

2000
On the Hardness of 4-coloring a 3-colorable Graph
Electronic Colloquium on Computational Complexity (ECCC), 2000

Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC), 2000

Algorithmic aspects of clique-transversal and clique-independent sets.
Discrete Applied Mathematics, 2000

List decoding algorithms for certain concatenated codes.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Query strategies for priced information (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

"Soft-decision" Decoding of Chinese Remainder Codes.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Hardness of Approximate Hypergraph Coloring.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Combinatorial feature selection problems.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

On Representations of Algebraic-Geometric Codes for List Decoding.
Proceedings of the Algorithms, 2000

On the Hardness of 4-Coloring a 3-Colorable Graph.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

Inapproximability results for set splitting and satisfiability problems with no mixed clauses.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Improved decoding of Reed-Solomon and algebraic-geometry codes.
IEEE Trans. Information Theory, 1999

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses
Electronic Colloquium on Computational Complexity (ECCC), 1999

Enumerative aspects of certain subclasses of perfect graphs.
Discrete Mathematics, 1999

Maximum Cut on Line and Total Graphs.
Discrete Applied Mathematics, 1999

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The 2-Catalog Segmentation Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Multiclass Learning, Boosting, and Error-Correcting Codes.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998
A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds.
Inf. Process. Lett., 1998

Improved decoding of Reed-Solomon and algebraic-geometric codes.
Electronic Colloquium on Computational Complexity (ECCC), 1998

A tight characterization of NP with 3 query PCPs
Electronic Colloquium on Computational Complexity (ECCC), 1998

The Vertex-Disjoint Triangles Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Tight Characterization of NP with 3 Query PCPs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998