Venkatesan Guruswami
According to our database^{1}, Venkatesan Guruswami
authored at least 369 papers
between 1998 and 2018.
Collaborative distances :
Collaborative distances :
Awards
ACM Fellow
ACM Fellow 2017, "For contributions to algorithmic coding theory, pseudorandomness and the complexity of approximate optimization".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at orcid.org

at isni.org

at id.loc.gov

at dl.acm.org
On csauthors.net:
Bibliography
2018
Efficient LowRedundancy 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 FredmanKomló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 FredmanKomlós for perfect khashing.
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 TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.
Proceedings of the TwentyNinth Annual ACMSIAM 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 ReedSolomon Codes.
IEEE Trans. Information Theory, 2017
Deletion Codes in the HighNoise and HighRate Regimes.
IEEE Trans. Information Theory, 2017
Efficiently ListDecodable Punctured ReedMuller 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 HTransversal/Packing.
SIAM J. Discrete Math., 2017
Nearly Optimal NPHardness of Unique Coverage.
SIAM J. Comput., 2017
SuperPolylogarithmic Hypergraph Coloring Hardness via LowDegree Long Codes.
SIAM J. Comput., 2017
(2+ε)Sat Is NPhard.
SIAM J. Comput., 2017
Nonmalleable Coding Against BitWise and SplitState 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 2to2 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 ListDecodability of Random Linear RankMetric Codes.
CoRR, 2017
On Maximally Recoverable Local Reconstruction Codes.
CoRR, 2017
MDS Code Constructions with Small Subpacketization and Nearoptimal Repair Bandwidth.
CoRR, 2017
Optimal rate list decoding over bounded alphabets using algebraicgeometric 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 Subpacketization and Nearoptimal Repair Bandwidth.
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
∊MSR codes with small subpacketization.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017
An improved bound on the zeroerror listdecoding 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
SumofSquares Certificates for Maxima of Random Tensors on the Sphere.
Proceedings of the Approximation, 2017
2016
Decoding ReedSolomon Codes.
Encyclopedia of Algorithms, 2016
Simple Proof of Hardness of Feedback Vertex Set.
Theory of Computing, 2016
Explicit ListDecodable RankMetric and Subspace Codes via Subspace Designs.
IEEE Trans. Information Theory, 2016
Capacity of NonMalleable 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 subpacketization and nearoptimal repair bandwidth.
CoRR, 2016
Codes correcting deletions in oblivious and random models.
CoRR, 2016
Efficiently decodable insertion/deletion codes for highnoise and highrate 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 Reedsolomon codes.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Nearly Optimal NPHardness of Unique Coverage.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
An improved bound on the fraction of correctable deletions.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Efficient LowRedundancy Codes for Correcting Multiple Deletions.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Efficiently decodable insertion/deletion codes for highnoise and highrate 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 CommunicationAssisted 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 kUniform kPartite Hypergraphs.
SIAM J. Discrete Math., 2015
Optimal rate algebraic list decoding using narrow ray class fields.
J. Comb. Theory, Ser. A, 2015
Nearly Optimal NPHardness 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 LowRedundancy 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 ReedSolomon Codes.
CoRR, 2015
Inapproximability of $H$Transversal/Packing.
CoRR, 2015
Efficient list decoding of punctured ReedMuller codes.
CoRR, 2015
An improved bound on the fraction of correctable deletions.
CoRR, 2015
Efficient LowRedundancy Codes for Correcting Multiple Deletions.
CoRR, 2015
Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises.
CoRR, 2015
Limitations on Testable AffineInvariant Codes in the HighRate Regime.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
Strong Inapproximability Results on Balanced RainbowColorable Hypergraphs.
Proceedings of the TwentySixth Annual ACMSIAM 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 Highnoise and Highrate Regimes.
Proceedings of the Approximation, 2015
Towards a Characterization of Approximation Resistance for Symmetric CSPs.
Proceedings of the Approximation, 2015
Inapproximability of HTransversal/Packing.
Proceedings of the Approximation, 2015
Dimension Expanders via Rank Condensers.
Proceedings of the Approximation, 2015
Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises.
Proceedings of the Approximation, 2015
2014
Combinatorial Limitations of AverageRadius ListDecoding.
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 AffineInvariant Codes in the HighRate Regime.
Electronic Colloquium on Computational Complexity (ECCC), 2014
Strong Inapproximability Results on Balanced RainbowColorable 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 highnoise and highrate 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
Nonmalleable Coding against BitWise and SplitState Tampering.
Proceedings of the Theory of Cryptography  11th Theory of Cryptography Conference, 2014
Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes.
Proceedings of the Symposium on Theory of Computing, 2014
Optimal rate list decoding of folded algebraicgeometric codes over constantsized alphabets.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Complexity of approximating CSP with balance / hard constraints.
Proceedings of the Innovations in Theoretical Computer Science, 2014
Capacity of nonmalleable codes.
Proceedings of the Innovations in Theoretical Computer Science, 2014
(2 + epsilon)Sat Is NPHard.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
Hitting Sets for LowDegree Polynomials with Optimal Density.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014
Evading Subspaces Over Large Fields and Explicit Listdecodable Rankmetric Codes.
Proceedings of the Approximation, 2014
2013
Improved Inapproximability Results for Maximum kColorable Subgraph.
Theory of Computing, 2013
LinearAlgebraic List Decoding for Variants of ReedSolomon Codes.
IEEE Trans. Information Theory, 2013
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
SIAM J. Comput., 2013
NonMalleable Coding Against Bitwise and SplitState Tampering.
IACR Cryptology ePrint Archive, 2013
Capacity of NonMalleable Codes.
IACR Cryptology ePrint Archive, 2013
Hitting Sets for LowDegree 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 algebraicgeometric codes over constantsized alphabets.
Electronic Colloquium on Computational Complexity (ECCC), 2013
Explicit rankmetric codes listdecodable with optimal redundancy.
Electronic Colloquium on Computational Complexity (ECCC), 2013
Inapproximability of Minimum Vertex Cover on kuniform kpartite 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
Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes.
Electronic Colloquium on Computational Complexity (ECCC), 2013
PCPs via lowdegree long code and hardness for constrained hypergraph coloring.
Electronic Colloquium on Computational Complexity (ECCC), 2013
NonMalleable Coding Against Bitwise and SplitState Tampering.
Electronic Colloquium on Computational Complexity (ECCC), 2013
Capacity of NonMalleable Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2013
(2+ε)SAT is NPhard.
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 rankmetric codes listdecodable with optimal redundancy.
CoRR, 2013
Rounding Lasserre SDPs using column selection and spectrumbased approximation schemes for graph partitioning and Quadratic IPs.
CoRR, 2013
Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes.
CoRR, 2013
NonMalleable Coding Against Bitwise and SplitState Tampering.
CoRR, 2013
Capacity of NonMalleable 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 reedsolomon, algebraicgeometric, and gabidulin subcodes up to the singleton bound.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Approximating NonUniform Sparsest Cut Via Generalized Spectra.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
Proceedings of the TwentyFourth Annual ACMSIAM 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 LowDegree 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 AverageRadius List Decoding.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013
2012
Tight Bounds on the Approximability of AlmostSatisfiable 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 ReedSolomon, AlgebraicGeometric, 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
Linearalgebraic list decoding for variants of ReedSolomon 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 columnbased lowrank matrix reconstruction.
Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012
Bypassing UGC from some optimal geometric inapproximability results.
Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012
Polynomial integrality gaps for strong SDP relaxations of Densest ksubgraph.
Proceedings of the TwentyThird Annual ACMSIAM 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 ListDecodable varepsilonBiased Codes.
IEEE Trans. Information Theory, 2011
On the ListDecodability 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 NonUniform Sparsity via Generalized Spectra
CoRR, 2011
Polynomial integrality gaps for strong SDP relaxations of Densest ksubgraph
CoRR, 2011
Optimal rate list decoding via derivative codes
CoRR, 2011
Linearalgebraic list decoding of folded ReedSolomon codes
CoRR, 2011
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
CoRR, 2011
Optimal ColumnBased LowRank Matrix Reconstruction
CoRR, 2011
The query complexity of estimating weighted averages.
Acta Inf., 2011
Tight Bounds on the Approximability of Almostsatisfiable Horn SAT and Exact Hitting Set.
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
Finding AlmostPerfect 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
LinearAlgebraic List Decoding of Folded ReedSolomon 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 listdecodable 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 Almostsatisfiable 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 ListDecodability 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 ListDecodability of Random Linear Codes
CoRR, 2010
Almost Euclidean subspaces of l _{1}^{N} VIA expander codes.
Combinatorica, 2010
Inapproximability of EdgeDisjoint Paths and low congestion routing on undirected graphs.
Combinatorica, 2010
On the listdecodability of random linear codes.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
On the Inapproximability of Vertex Cover on kPartite kUniform Hypergraphs.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
SDP Gaps for 2to1 and Other LabelCover 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 3Query 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 ParvareshVardy codes.
J. ACM, 2009
Improved Inapproximability Results for Maximum kColorable Subgraph.
Electronic Colloquium on Computational Complexity (ECCC), 2009
Hardness of Solving Sparse Overdetermined Linear Systems: A 3Query PCP over Integers.
Electronic Colloquium on Computational Complexity (ECCC), 2009
Artin automorphisms, Cyclotomic function fields, and Folded listdecodable 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 kColorable Subgraph
CoRR, 2009
Error correction up to the informationtheoretic limit.
Commun. ACM, 2009
Artin automorphisms, cyclotomic function fields, and folded listdecodable 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 lowerbounded 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 CodesA 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 kColorable Subgraph.
Proceedings of the Approximation, 2009
2008
Decoding ReedSolomon Codes.
Proceedings of the Encyclopedia of Algorithms, 2008
Explicit Codes Achieving List Decoding Capacity: ErrorCorrection With Optimal Redundancy.
IEEE Trans. Information Theory, 2008
Correlated algebraicgeometric codes: Improved list decoding over bounded alphabets.
Math. Comput., 2008
Concatenated codes can achieve listdecoding capacity.
Electronic Colloquium on Computational Complexity (ECCC), 2008
Soft decoding, dual BCH codes, and better listdecodable epsbiased codes.
Electronic Colloquium on Computational Complexity (ECCC), 2008
Constraint Satisfaction over a NonBoolean Domain: Approximation algorithms and UniqueGames 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 listdecodable codes
CoRR, 2008
Hardness Amplification via SpaceEfficient Direct Products.
Computational Complexity, 2008
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica, 2008
Concatenated codes can achieve listdecoding capacity.
Proceedings of the Nineteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2008
Almost Euclidean subspaces of l^{N}_{1} via expander codes.
Proceedings of the Nineteenth Annual ACMSIAM 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 ErrorCorrection 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 ListDecodable eBiased 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 NonBoolean Domain: Approximation Algorithms and UniqueGames Hardness.
Proceedings of the Approximation, 2008
Euclidean Sections of with Sublinear Randomness and ErrorCorrection over the Reals.
Proceedings of the Approximation, 2008
2007
Guessing secrets efficiently via list decoding.
ACM Trans. Algorithms, 2007
Better Binary ListDecodable Codes via Multilevel Concatenation.
Electronic Colloquium on Computational Complexity (ECCC), 2007
Almost Euclidean subspaces of ℓ_{1}^{N} 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 edgedisjoint 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 3query 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 ParvareshVardy Codes.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007
Better Binary ListDecodable 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 ReedSolomon 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 LowDensity Parity Check Codes (A Survey).
Electronic Colloquium on Computational Complexity (ECCC), 2006
Iterative Decoding of LowDensity Parity Check Codes.
Bulletin of the EATCS, 2006
Iterative Decoding of LowDensity Parity Check Codes (A Survey)
CoRR, 2006
Explicit capacityachieving listdecodable 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 ACMSIAM Symposium on Discrete Algorithms, 2006
Hardness Amplification Via SpaceEfficient 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 2Query Codeword Testing with NearPerfect 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 AlgebraicGeometric Codes: Improved List Decoding over Bounded Alphabets.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
2005
Maximumlikelihood decoding of ReedSolomon codes is NPhard.
IEEE Trans. Information Theory, 2005
Lineartime encodable/decodable codes with nearoptimal 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 CapacityAchieving ListDecodable Codes
Electronic Colloquium on Computational Complexity (ECCC), 2005
Algebraicgeometric generalizations of the ParvareshVardy codes
Electronic Colloquium on Computational Complexity (ECCC), 2005
Hardness amplification via spaceefficient 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: Errorcorrection 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 ReedSolomon codes.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Maximumlikelihood decoding of ReedSolomon codes is NPhard.
Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005
On profitmaximizing envyfree pricing.
Proceedings of the Sixteenth Annual ACMSIAM 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 1in k SAT.
Proceedings of the Approximation, 2005
Tolerant Locally Testable Codes.
Proceedings of the Approximation, 2005
2004
Guest column: errorcorrecting codes and expander graphs.
SIGACT News, 2004
On the Hardness of 4Coloring a 3Colorable 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
Maximumlikelihood decoding of ReedSolomon codes is NPhard
Electronic Colloquium on Computational Complexity (ECCC), 2004
Maximumlikelihood decoding of ReedSolomon Codes is NPhard
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 GilbertVarshamov bound for low rates.
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
LinearTime List Decoding in ErrorFree 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 ErrorCorrecting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition)
Lecture Notes in Computer Science 3282, Springer, ISBN: 3540240519, 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
Nearoptimal hardness results and approximation algorithms for edgedisjoint 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 ACMSIAM Symposium on Discrete Algorithms, 2003
Embeddings and nonapproximability of geometric problems.
Proceedings of the Fourteenth Annual ACMSIAM 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 kUniform Hypergraphs is Hard to Approximate within Factor (k3epsilon)
Electronic Colloquium on Computational Complexity (ECCC), 2002
Nearoptimal lineartime codes for unique decoding and new listdecodable 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 ACMSIAM 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 algebraicgeometry codes.
IEEE Trans. Information Theory, 2001
Constructions of Codes from Number Fields
Electronic Colloquium on Computational Complexity (ECCC), 2001
The K_{r}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
ExpanderBased 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 4coloring a 3colorable Graph
Electronic Colloquium on Computational Complexity (ECCC), 2000
Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC), 2000
Algorithmic aspects of cliquetransversal and cliqueindependent sets.
Discrete Applied Mathematics, 2000
List decoding algorithms for certain concatenated codes.
Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
Query strategies for priced information (extended abstract).
Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
"Softdecision" 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 AlgebraicGeometric Codes for List Decoding.
Proceedings of the Algorithms, 2000
On the Hardness of 4Coloring a 3Colorable 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 ReedSolomon and algebraicgeometry 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
NearOptimal Hardness Results and Approximation Algorithms for EdgeDisjoint Paths and Related Problems.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
The 2Catalog Segmentation Problem.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
Multiclass Learning, Boosting, and ErrorCorrecting 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 ReedSolomon and algebraicgeometric 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 VertexDisjoint Triangles Problem.
Proceedings of the GraphTheoretic Concepts in Computer Science, 1998
Improved Decoding of ReedSolomon and AlgebraicGeometric 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