Venkatesan Guruswami

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

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

2018
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth.
IEEE Trans. Information Theory, 2018

Secret Sharing with Binary Shares.
IACR Cryptology ePrint Archive, 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

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

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

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

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

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

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
Efficiently List-Decodable Punctured Reed-Muller Codes.
IEEE Trans. Information Theory, 2017

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

(2+ε)-Sat Is NP-hard.
SIAM J. Comput., 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008).
SIAM J. Comput., 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

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

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

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

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

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

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

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

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

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}.
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 list-decodability of random linear codes.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2006
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tolerant Locally Testable Codes.
Proceedings of the Approximation, 2005

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The Kr-Packing Problem.
Computing, 2001

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


  Loading...