Venkatesan Guruswami

According to our database1, Venkatesan Guruswami authored at least 240 papers between 1998 and 2020.

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

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Coding Against Deletions in Oblivious and Online Models.
IEEE Trans. Inf. Theory, 2020

An Improved Bound on the Zero-Error List-Decoding 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 list-decoding and list-recovery of random linear codes.
CoRR, 2020

A locality-based approach for coded computation.
CoRR, 2020

Arikan meets Shannon: polar codes with near-optimal 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 ACM-SIAM Symposium on Discrete Algorithms, 2020

Leakage-Resilient Secret Sharing in Non-Compartmentalized Models.
Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

d-To-1 Hardness of Coloring 3-Colorable 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 near-optimal 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 List-Decoding 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 Sub-Packetization of MSR Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Non-Malleable 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 ACM-SIAM Symposium on Discrete Algorithms, 2019

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization.
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 Sub-Packetization and Near-Optimal 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 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→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 Rainbow-Colorable Hypergraphs.
Combinatorica, 2018

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

On the List-Decodability of Random Linear Rank-Metric 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 optimal-length 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 Reed-Solomon Codes.
IEEE Trans. Inf. Theory, 2017

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

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

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

Inapproximability of H-Transversal/Packing.
SIAM J. Discret. Math., 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

Optimal rate list decoding over bounded alphabets using algebraic-geometric codes.
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

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

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 Comput., 2016

Explicit List-Decodable Rank-Metric 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 sub-packetization and near-optimal 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 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

2015
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs.
SIAM J. Discret. 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

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

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

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

2014
Combinatorial Limitations of Average-Radius List-Decoding.
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 Affine-Invariant Codes in the High-Rate 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 NP-Hard.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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 Comput., 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

Complexity of approximating CSP with Balance / Hard Constraints.
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

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

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

Rounding Lasserre SDPs using column selection and spectrum-based 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 Non-Uniform Sparsest Cut Via Generalized Spectra.
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

2012
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set.
Theory 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

Optimal column-based low-rank matrix reconstruction.
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

2011
Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased 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 Non-Uniform Sparsity via Generalized Spectra
CoRR, 2011

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

The query complexity of estimating weighted averages.
Acta Informatica, 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. Inf. Theory, 2010

The existence of concatenated codes list-decodable 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 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

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

2009
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.
J. ACM, 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

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

MaxMin allocation via degree lower-bounded arborescences.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 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

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

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.
IEEE Trans. Inf. 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

Hardness Amplification via Space-Efficient Direct Products.
Comput. Complex., 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica, 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

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

Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Comput. Complex., 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

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 Reed-Solomon 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 Low-Density Parity Check Codes (A Survey).
Electronic Colloquium on Computational Complexity (ECCC), 2006

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

List Decoding in Average-Case Complexity and Pseudorandomness.
Proceedings of the 2006 IEEE Information Theory Workshop, 2006

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

2005
Linear-time encodable/decodable codes with near-optimal 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 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

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

The complexity of the covering radius problem.
Comput. Complex., 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

The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
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. Discret. Math., 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

Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
Algorithmica, 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. Inf. 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

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

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

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. Inf. Theory, 2001

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

The Kr-Packing Problem.
Computing, 2001

Expander-Based 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 clique-transversal and clique-independent sets.
Discret. Appl. Math., 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

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

1999
Improved decoding of Reed-Solomon and algebraic-geometry 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 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


  Loading...