Venkatesan Guruswami
According to our database^{1},
Venkatesan Guruswami
authored at least 240 papers
between 1998 and 2020.
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 wikidata.org

at orcid.org

at id.loc.gov

at cs.cmu.edu

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
2020
Coding Against Deletions in Oblivious and Online Models.
IEEE Trans. Inf. Theory, 2020
An Improved Bound on the ZeroError ListDecoding Capacity of the 4/3 Channel.
IEEE Trans. Inf. Theory, 2020
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms.
SIAM J. Discret. Math., 2020
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.
Electronic Colloquium on Computational Complexity (ECCC), 2020
Bounds for listdecoding and listrecovery of random linear codes.
CoRR, 2020
A localitybased approach for coded computation.
CoRR, 2020
Arikan meets Shannon: polar codes with nearoptimal convergence to channel capacity.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs.
Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, 2020
LeakageResilient Secret Sharing in NonCompartmentalized Models.
Proceedings of the 1st Conference on InformationTheoretic Cryptography, 2020
dTo1 Hardness of Coloring 3Colorable Graphs with O(1) Colors.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
2019
How Long Can Optimal Locally Repairable Codes Be?
IEEE Trans. Inf. Theory, 2019
Polynomial Time Decodable Codes for the Binary Deletion Channel.
IEEE Trans. Inf. Theory, 2019
$d$to$1$ Hardness of Coloring $4$colorable Graphs with $O(1)$ colors.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Ar?kan meets Shannon: Polar codes with nearoptimal convergence to channel capacity.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Revisiting Alphabet Reduction in Dinur's PCP.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Optimally Resilient Codes for ListDecoding from Insertions and Deletions.
Electronic Colloquium on Computational Complexity (ECCC), 2019
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Bridging between 0/1 and Linear Programming via Random Walks.
Electronic Colloquium on Computational Complexity (ECCC), 2019
An Exponential Lower Bound on the SubPacketization of MSR Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2019
NonMalleable Secret Sharing against Affine Tampering.
CoRR, 2019
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Nearoptimal Repair of ReedSolomon Codes with Low Subpacketization.
Proceedings of the IEEE International Symposium on Information Theory, 2019
Algorithmic Polarization for Hidden Markov Models.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Streaming Hardness of Unique Games.
Proceedings of the Approximation, 2019
2018
MDS Code Constructions With Small SubPacketization and NearOptimal Repair Bandwidth.
IEEE Trans. Inf. Theory, 2018
Secret Sharing with Binary Shares.
IACR Cryptol. ePrint Arch., 2018
Lossless dimension expanders via linearized polynomials and subspace designs.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Beating FredmanKomlós for perfect khashing.
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→q Norms.
Electronic Colloquium on Computational Complexity (ECCC), 2018
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).
Dagstuhl Reports, 2018
εMSR Codes: Contacting Fewer Code Blocks for Exact Repair.
CoRR, 2018
Strong Inapproximability Results on Balanced RainbowColorable Hypergraphs.
Combinatorica, 2018
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
On the ListDecodability of Random Linear RankMetric Codes.
Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018
∊MSR Codes: Contacting Fewer Code Blocks for Exact Repair.
Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018
Polar Codes with Exponentially Small Error at Finite Block Length.
Proceedings of the Approximation, 2018
Explicit optimallength locally repairable codes of distance 5.
Proceedings of the 56th Annual Allerton Conference on Communication, 2018
2017
Towards a Characterization of Approximation Resistance for Symmetric CSPs.
Theory Comput., 2017
Repairing ReedSolomon Codes.
IEEE Trans. Inf. Theory, 2017
Deletion Codes in the HighNoise and HighRate Regimes.
IEEE Trans. Inf. Theory, 2017
Efficiently ListDecodable Punctured ReedMuller Codes.
IEEE Trans. Inf. Theory, 2017
An Improved Bound on the Fraction of Correctable Deletions.
IEEE Trans. Inf. Theory, 2017
Inapproximability of HTransversal/Packing.
SIAM J. Discret. Math., 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
Optimal rate list decoding over bounded alphabets using algebraicgeometric codes.
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
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
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 Comput., 2016
Explicit ListDecodable RankMetric and Subspace Codes via Subspace Designs.
IEEE Trans. Inf. Theory, 2016
Bypassing UGC from Some Optimal Geometric Inapproximability Results.
ACM Trans. Algorithms, 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
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey).
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
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
2015
Inapproximability of Minimum Vertex Cover on kUniform kPartite Hypergraphs.
SIAM J. Discret. 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
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
Efficient list decoding of punctured ReedMuller codes.
CoRR, 2015
Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises.
Proceedings of the Approximation, 2015
2014
Combinatorial Limitations of AverageRadius ListDecoding.
IEEE Trans. Inf. Theory, 2014
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems.
SIAM J. Optim., 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
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
(2 + epsilon)Sat Is NPHard.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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 Comput., 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
Complexity of approximating CSP with Balance / Hard Constraints.
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
Capacity of NonMalleable Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2013
(2+ε)SAT is NPhard.
Electronic Colloquium on Computational Complexity (ECCC), 2013
Rounding Lasserre SDPs using column selection and spectrumbased approximation schemes for graph partitioning and Quadratic IPs.
CoRR, 2013
CopyCatch: stopping group attacks by spotting lockstep behavior in social networks.
Proceedings of the 22nd International World Wide Web Conference, 2013
Approximating NonUniform Sparsest Cut Via Generalized Spectra.
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
2012
Tight Bounds on the Approximability of AlmostSatisfiable Horn SAT and Exact Hitting Set.
Theory 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
Optimal columnbased lowrank matrix reconstruction.
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
2011
Soft Decoding, Dual BCH Codes, and Better ListDecodable varepsilonBiased Codes.
IEEE Trans. Inf. Theory, 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
The query complexity of estimating weighted averages.
Acta Informatica, 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. Inf. Theory, 2010
The existence of concatenated codes listdecodable up to the hamming bound.
IEEE Trans. Inf. Theory, 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
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
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 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
2009
Unbalanced expanders and randomness extractors from ParvareshVardy codes.
J. ACM, 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
Error correction up to the informationtheoretic limit.
Commun. ACM, 2009
MaxMin allocation via degree lowerbounded arborescences.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 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
2008
Decoding ReedSolomon Codes.
Proceedings of the Encyclopedia of Algorithms  2008 Edition, 2008
Explicit Codes Achieving List Decoding Capacity: ErrorCorrection With Optimal Redundancy.
IEEE Trans. Inf. 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
Hardness Amplification via SpaceEfficient Direct Products.
Comput. Complex., 2008
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica, 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
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
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Comput. Complex., 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
List Decoding and Pseudorandom Constructions.
Proceedings of the Applied Algebra, 2007
2006
Correlation Clustering with a Fixed Number of Clusters.
Theory Comput., 2006
Limits to List Decoding ReedSolomon Codes.
IEEE Trans. Inf. 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.
Bull. EATCS, 2006
List Decoding in AverageCase Complexity and Pseudorandomness.
Proceedings of the 2006 IEEE Information Theory Workshop, 2006
On 2Query Codeword Testing with NearPerfect Completeness.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006
2005
Lineartime encodable/decodable codes with nearoptimal rate.
IEEE Trans. Inf. 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
Tolerant Locally Testable Codes
Electronic Colloquium on Computational Complexity (ECCC), 2005
The complexity of the covering radius problem.
Comput. Complex., 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
The Complexity of Making Unique Choices: Approximating 1in k SAT.
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. Discret. Math., 2004
Guest Editors' foreword.
J. Comput. Syst. Sci., 2004
Maximumlikelihood decoding of ReedSolomon codes is NPhard
Electronic Colloquium on Computational Complexity (ECCC), 2004
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
Algorithmica, 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. Inf. 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
Linear time encodable and list decodable codes.
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
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. Inf. Theory, 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
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. Inf. Theory, 2001
Constructions of Codes from Number Fields
Electronic Colloquium on Computational Complexity (ECCC), 2001
The K_{r}Packing Problem.
Computing, 2001
ExpanderBased Constructions of Efficiently Decodable Codes.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC), 2000
Algorithmic aspects of cliquetransversal and cliqueindependent sets.
Discret. Appl. Math., 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
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
1999
Improved decoding of ReedSolomon and algebraicgeometry codes.
IEEE Trans. Inf. 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.
Discret. Math., 1999
Maximum Cut on Line and Total Graphs.
Discret. Appl. Math., 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