Venkatesan Guruswami

Affiliations:
  • University of Berkeley, Department of EECS, Berkeley, CA, USA
  • Carnegie Mellon University, Pittsburgh, USA (former)


According to our database1, Venkatesan Guruswami authored at least 292 papers between 1998 and 2023.

Collaborative distances:
  • Dijkstra number2 of two.
  • 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 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Efficient Linear and Affine Codes for Correcting Insertions/Deletions.
SIAM J. Discret. Math., June, 2023

Inapproximability of Matrix p → q Norms.
SIAM J. Comput., February, 2023

Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions.
IEEE Trans. Inf. Theory, 2023

Baby PIH: Parameterized Inapproximability of Min CSP.
Electron. Colloquium Comput. Complex., 2023

Parameterized Inapproximability Hypothesis under ETH.
Electron. Colloquium Comput. Complex., 2023

Quantum Locally Recoverable Codes.
Electron. Colloquium Comput. Complex., 2023

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets.
Electron. Colloquium Comput. Complex., 2023

Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields.
Electron. Colloquium Comput. Complex., 2023

Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding.
CoRR, 2023

Improved rate-distance trade-offs for quantum codes with restricted connectivity.
CoRR, 2023

Binary Error-Correcting Codes with Minimal Noiseless Feedback.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

SDPs and Robust Satisfiability of Promise CSP.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i><sub>p</sub></i> Norms.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars.
Proceedings of the IEEE International Symposium on Information Theory, 2023

How Many Matrices Should I Prepare To Polarize Channels Optimally Fast?
Proceedings of the IEEE International Symposium on Information Theory, 2023

On expanding the toolkit of locality-based coded computation to the coordinates of inputs.
Proceedings of the IEEE International Symposium on Information Theory, 2023

Hardness of Learning Boolean Functions from Label Proportions.
Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble.
Proceedings of the Approximation, 2023

2022
Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity.
IEEE Trans. Inf. Theory, 2022

Threshold Rates for Properties of Random Codes.
IEEE Trans. Inf. Theory, 2022

Bounds for List-Decoding and List-Recovery of Random Linear Codes.
IEEE Trans. Inf. Theory, 2022

Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.
SIAM J. Comput., 2022

Beating Fredman-Komlós for perfect <i>k</i>-hashing.
J. Comb. Theory, Ser. A, 2022

Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes.
J. ACM, 2022

General Strong Polarization.
J. ACM, 2022

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness.
Electron. Colloquium Comput. Complex., 2022

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ<sub>p</sub> Norms.
Electron. Colloquium Comput. Complex., 2022

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation.
Electron. Colloquium Comput. Complex., 2022

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).
Dagstuhl Reports, 2022

Sparsity and 𝓁<sub>p</sub>-Restricted Isometry.
CoRR, 2022

CNF Satisfiability in a Subspace and Related Problems.
Algorithmica, 2022

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Punctured Low-Bias Codes Behave Like Random Linear Codes.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

ℓ<sub>p</sub>-Spread and Restricted Isometry Properties of Sparse Random Matrices.
Proceedings of the 37th Computational Complexity Conference, 2022

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number.
Proceedings of the Approximation, 2022

Accelerating Polarization via Alphabet Extension.
Proceedings of the Approximation, 2022

2021
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound.
IEEE Trans. Inf. Theory, 2021

An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes.
IEEE Trans. Inf. Theory, 2021

The Quest for Strong Inapproximability Results with Perfect Completeness.
ACM Trans. Algorithms, 2021

Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity.
Electron. Colloquium Comput. Complex., 2021

The zero-rate threshold for adversarial bit-deletions is less than 1/2.
Electron. Colloquium Comput. Complex., 2021

Improved Maximally Recoverable LRCs using Skew Polynomials.
Electron. Colloquium Comput. Complex., 2021

Conditional Dichotomy of Boolean Ordered Promise CSPs.
Electron. Colloquium Comput. Complex., 2021

Revisiting a Lower Bound on the Redundancy of Linear Batch Codes.
Electron. Colloquium Comput. Complex., 2021

Visible Rank and Codes with Locality.
Electron. Colloquium Comput. Complex., 2021

𝓁<sub>p</sub>-Spread Properties of Sparse Matrices.
CoRR, 2021

Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs.
Comb., 2021

Strongly refuting all semi-random Boolean CSPs.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A locality-based lens for coded computation.
Proceedings of the IEEE International Symposium on Information Theory, 2021

Linear Programming Bounds for Almost-Balanced Binary Codes.
Proceedings of the IEEE International Symposium on Information Theory, 2021

Linear Shannon Capacity of Cayley Graphs.
Proceedings of the IEEE International Symposium on Information Theory, 2021

Sharp Threshold Rates for Random Codes.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair.
IEEE Trans. Inf. Theory, 2020

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

Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields.
IEEE Trans. Inf. Theory, 2020

Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities.
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 Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.
SIAM J. Comput., 2020

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture.
Electron. Colloquium Comput. Complex., 2020

Pseudobinomiality of the Sticky Random Walk.
Electron. Colloquium Comput. Complex., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.
Electron. Colloquium Comput. Complex., 2020

An Algorithmic Study of the Hypergraph Turán Problem.
CoRR, 2020

A locality-based approach for coded computation.
CoRR, 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.
Electron. Colloquium Comput. Complex., 2019

Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity.
Electron. Colloquium Comput. Complex., 2019

Revisiting Alphabet Reduction in Dinur's PCP.
Electron. Colloquium Comput. Complex., 2019

Optimally Resilient Codes for List-Decoding from Insertions and Deletions.
Electron. Colloquium Comput. Complex., 2019

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.
Electron. Colloquium Comput. Complex., 2019

Bridging between 0/1 and Linear Programming via Random Walks.
Electron. Colloquium Comput. Complex., 2019

An Exponential Lower Bound on the Sub-Packetization of MSR Codes.
Electron. Colloquium Comput. Complex., 2019

Non-Malleable Secret Sharing against Affine Tampering.
CoRR, 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

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

Beating Fredman-Komlós for perfect k-hashing.
Electron. Colloquium Comput. Complex., 2018

Combining LPs and Ring Equations via Structured Polymorphisms.
Electron. Colloquium Comput. Complex., 2018

Approximating Operator Norms via Generalized Krivine Rounding.
Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.
Electron. Colloquium Comput. Complex., 2018

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).
Dagstuhl Reports, 2018

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs.
Comb., 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. Cryptol., 2017

Subspace Designs based on Algebraic Function Fields.
Electron. Colloquium Comput. Complex., 2017

Hardness of Rainbow Coloring Hypergraphs.
Electron. Colloquium Comput. Complex., 2017

On Maximally Recoverable Local Reconstruction Codes.
Electron. Colloquium Comput. Complex., 2017

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2016

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.
Electron. Colloquium Comput. Complex., 2016

New hardness results for graph and hypergraph colorings.
Electron. Colloquium Comput. Complex., 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.
Electron. Colloquium Comput. Complex., 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.
Comb., 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.
Electron. Colloquium Comput. Complex., 2015

An improved bound on the fraction of correctable deletions.
Electron. Colloquium Comput. Complex., 2015

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2014

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.
Electron. Colloquium Comput. Complex., 2014

Inapproximability of Feedback Vertex Set for Bounded Length Cycles.
Electron. Colloquium Comput. Complex., 2014

Dimension Expanders via Rank Condensers.
Electron. Colloquium Comput. Complex., 2014

Communication with Imperfectly Shared Randomness.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2013

Polar Codes: Speed of polarization and polynomial gap to capacity.
Electron. Colloquium Comput. Complex., 2013

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets.
Electron. Colloquium Comput. Complex., 2013

Explicit rank-metric codes list-decodable with optimal redundancy.
Electron. Colloquium Comput. Complex., 2013

Complexity of approximating CSP with Balance / Hard Constraints.
Electron. Colloquium Comput. Complex., 2013

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
Electron. Colloquium Comput. Complex., 2013

PCPs via low-degree long code and hardness for constrained hypergraph coloring.
Electron. Colloquium Comput. Complex., 2013

Capacity of Non-Malleable Codes.
Electron. Colloquium Comput. Complex., 2013

(2+ε)-SAT is NP-hard.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2012

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound.
Electron. Colloquium Comput. Complex., 2012

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding.
Electron. Colloquium Comput. Complex., 2012

Linear-algebraic list decoding for variants of Reed-Solomon codes.
Electron. Colloquium Comput. Complex., 2012

Faster SDP hierarchy solvers for local rounding algorithms.
Electron. Colloquium Comput. Complex., 2012

Combinatorial limitations of a strong form of list decoding.
Electron. Colloquium Comput. Complex., 2012

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
Electron. Colloquium Comput. Complex., 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 <i>k</i>-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.
Electron. Colloquium Comput. Complex., 2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2010

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate.
Electron. Colloquium Comput. Complex., 2010

On the List-Decodability of Random Linear Codes.
Electron. Colloquium Comput. Complex., 2010

Agnostic Learning of Monomials by Halfspaces is Hard.
Electron. Colloquium Comput. Complex., 2010

Almost Euclidean subspaces of <i>l</i> <sub>1</sub><sup><i>N</i></sup> VIA expander codes.
Comb., 2010

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

On the Inapproximability of Vertex Cover on <i>k</i>-Partite <i>k</i>-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.
Electron. Colloquium Comput. Complex., 2009

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes.
Electron. Colloquium Comput. Complex., 2009

Locally Testable Codes Require Redundant Testers.
Electron. Colloquium Comput. Complex., 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

Expander codes over reals, Euclidean sections, and compressed sensing.
Proceedings of the 47th Annual Allerton Conference on Communication, 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.
Electron. Colloquium Comput. Complex., 2008

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.
Electron. Colloquium Comput. Complex., 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.
Electron. Colloquium Comput. Complex., 2008

List Decoding Tensor Products and Interleaved Codes.
Electron. Colloquium Comput. Complex., 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 l<sup>N</sup><sub>1</sub> 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.
Electron. Colloquium Comput. Complex., 2007

Almost Euclidean subspaces of ℓ<sub>1</sub><sup>N</sup> via expander codes.
Electron. Colloquium Comput. Complex., 2007

Deterministic Hardness Amplification via Local GMD Decoding.
Electron. Colloquium Comput. Complex., 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.
Found. Trends Theor. Comput. Sci., 2006

Extractors and condensers from univariate polynomials.
Electron. Colloquium Comput. Complex., 2006

Hardness of Low Congestion Routing in Directed Graphs.
Electron. Colloquium Comput. Complex., 2006

Hardness of Learning Halfspaces with Noise.
Electron. Colloquium Comput. Complex., 2006

Iterative Decoding of Low-Density Parity Check Codes (A Survey).
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 2005

Algebraic-geometric generalizations of the Parvaresh-Vardy codes
Electron. Colloquium Comput. Complex., 2005

Tolerant Locally Testable Codes
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 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?
Electron. Colloquium Comput. Complex., 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?
Electron. Colloquium Comput. Complex., 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 2001

The K<sub>r</sub>-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
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs
Electron. Colloquium Comput. Complex., 1998

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


  Loading...