LIST DECODING OF ERROR-CORRECTING CODES Lecture Notes in Computer Science, Vol. 3282 Springer-Verlag 2005, 350 p., ISBN: 3-540-24051-9 Check prices & availability at Amazon; Booksamillion.

ALGORITHMIC RESULTS IN LIST DECODING, Foundations and Trends® in Theoretical Computer Science, Volume 2, Issue 2, 2007. You can download a free copy of the book (for personal use only) here. A printed and bound version of this article is available at a 40% discount from Now Publishers. This can be obtained by entering the promotional code TCS002002 on the order form at now publishers.

Following is a list of papers (co)-authored by me, arranged by topic/category. Recent papers (since 2005 or so) are not (yet) categorized by topic. Within each topic, the papers are ordered more or less in reverse chronological order of date of first publication. I also usually try to make only the most recent version (eg. the journal version/submission, if one exists) of the paper available.

• Publications (2006 onwards)
• Surveys
• Coding Theory
• Approximations Algorithms, Hardness of Approximations, and PCPs
• Other theory papers
• Theses
• Algorithmic and Structural Graph Theory

DBLP listing of publications

Google Scholar page

ACM Digital Library author page

Papers (2006-present)

• New constructions of pseudorandom codes, arXiv:2409.07580. (With S. Ghentiyala)
• Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates, arXiv:2408.09254 [quant-ph]. (With L. Golowich)
• Tight bounds for stream decodable error-correcting codes, arXiv:2407.06446. (With M. Gupta and M. Singhal)
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH, ECCC TR24-075. (With B. Lin, X. Ren, Y. Sun, and K. Wu)
• Exponential Time Approximation for Coloring 3-Colorable Graphs, arXiv:2406.15563. (With R. Jain)
• Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding, arXiv:2311.08283. (With Hsin-Po Wang)
• Quantum locally recoverable codes, SODA 2025, to appear. (With L. Golowich)

---



• Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles, FOCS 2024, to appear. (With O. Alrabiah)
• Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the sqrt(n) Dimension Threshold, FOCS 2024, to appear. (With T. Hsieh and P. Raghavendra)
• Decoding quasi-cyclic quantum LDPC codes, FOCS 2024, to appear (With L. Golowich)
• Capacity-Achieving Gray Codes, RANDOM 2024. (With H. Wang)
• Baby PIH: Parameterized Inapproximability of Min CSP, CCC 2024. (With X. Ren and S. Sandeep)
• Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically, ISIT 2024. (With H. Wang)
• Isolate and then Identify: Rethinking Adaptive Group Testing, ISIT 2024. (With H. Wang)
• Parameterized Inapproximability Hypothesis under ETH, STOC 2024, Best Paper Award. (With B. Lin, X. Ren, Y. Sun, and K. Wu)
• Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields, STOC 2024. (With O. Alrabiah and R. Li)
• AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets , SODA 2024. (With O. Alrabiah and R. Li)
• Improved rate-distance trade-offs for quantum codes with restricted connectivity, QIP 2024, arXiv:2307.03283 [quant-ph]. (With N. Baspin, A. Krishna, and R. Li)

---



• Hardness of Learning Boolean Functions from Label Proportions, FSTTCS 2023. (With R. Saket)
• Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold, FOCS 2023. (With T. Hsieh, P. Kothari, and P. Manohar)
• A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble, RANDOM 2023. (With Allan Li)
• SDPs and Robust Satisfiability of Promise CSP, STOC 2023. (With J. Brakensiek and S. Sandeep)
• Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all \ell_p norms, STOC 2023. (With H. Bennett, M. Cheraghchi, and J. Ribeiro)
• A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation, STOC 2023. (With O. Alrabiah, P. Kothari, and P. Manohar)
• Binary Error-Correcting Codes with Minimal Noiseless Feedback, STOC 2023. (With M. Gupta and R. Y. Zhang)
• How Many Matrices Should I Prepare to Polarize Channels Optimally Fast?, ISIT 2023. (With H. Wang)
• On Expanding the Toolkit of Locality-Based Coded Computation to the Coordinates of Inputs, ISIT 2023. (With M. Rudow and R. Vinayak)
• Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars, ISIT 2023. (With R. Gabrys and H. Wang)

---



• Punctured Low-Bias Codes Behave Like Random Linear Codes, FOCS 2022 (With J. Mosheiff)
• Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness, RANDOM 2022. (With X. Lyu and X. Wang)
• Accelerating Polarization via Alphabet Extension, RANDOM 2022. (With I. Duursma, R. Gabrys, T-C. Lin, and H-P. Wang)
• Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number, APPROX 2022. (With P. Kothari and P. Manohar)
• Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions, RANDOM 2022. (With R. Gabrys, J. Ribeiro, K. Wu)
• $\ell_p$-spread and restricted isometry properties of sparse random matrices, CCC 2022. (With P. Manohar and J. Mosheiff)
• Sparsity and $\ell_p$-restricted isometry, arXiv:2205.06738. (With P. Manohar and J. Mosheiff)
• Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random", STOC 2022. (With P. Kothari and P. Manohar)
• Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture, SODA 2022. (With S. Sandeep)
• Improved Maximally Recoverable LRCs using Skew Polynomials, IEEE Trans. Info. Theory, 2022. (With S. Gopi)

---



• The zero-rate threshold for adversarial bit-deletions is less than 1/2, FOCS 2021. (With X. He and R. Li)
• Revisiting a Lower Bound on the Redundancy of Linear Batch Codes, ECCC TR21-145. (With O. Alrabiah)
• Visible rank and codes with locality, RANDOM 2021. (With O. Alrabiah)
• CNF satisfiability in a subspace and related problems, IPEC 2021. (With V. Arvind)
• AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing, arxiv:2011.05223, 2021. (With R. Gabrys, S. Pattabiraman, V. Rana, J. Ribeiro, M. Cheraghchi, O. Milenkovic)
• Conditional Dichotomy of Boolean Ordered Promise CSPs, ICALP 2021. (With J. Brakensiek and S. Sandeep)
• Linear Shannon Capacity of Cayley Graphs, ISIT 2021. (With A. Riazanov)
• Linear Programming Bounds for Almost-Balanced Binary Codes, ISIT 2021. (With A. Riazanov)
• A locality-based lens for coded computation, ISIT 2021. (With M. Rudow and K. V. Rashmi)
• Strongly refuting all semi-random Boolean CSPs, SODA 2021. (With J. Abascal and P. Kothari)
• Explicit two-deletion codes with redundancy matching the existential bound, SODA 2021. (With J. Håstad)
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions, SODA 2021. (With K. Cheng, B. Haeupler, and X. Li)
• Pseudobinomiality of the sticky random walk, ITCS 2021. (With V. Kumar)
• Sharp threshold rates for random codes, ITCS 2021. (With J. Mosheiff, N. Resch, S. Silas, M. Wootters)

---



• Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity, STOC 2020. (With A. Riazanov and Min Ye)
• Optimally Resilient Codes for List-Decoding from Insertions and Deletions, STOC 2020. (With B. Haeupler and A. Shahrasbi)
• d-to-1 Hardness of Coloring 3-colorable Graphs with O(1) colors, ICALP 2020. (With S. Sandeep)
• Bounds for list-decoding and list-recovery of random linear codes, RANDOM 2020. (With R. Li, J. Mosheiff, N. Resch, S. Silas, M. Wootters)
• Revisiting Alphabet Reduction in Dinur's PCP, APPROX 2020. (With J. Oprsal and S. Sandeep)
• Leakage-Resilient Secret Sharing in Non-compartmentalized Models, ITC 2020. (With F. Lin, M. Cheraghchi, R. Safavi-Naini, H. Wang)
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs, SODA 2020. (With J. Brakensiek)

---



• Rainbow coloring hardness via low sensitivity polymorphisms, APPROX 2019. (With Sai Sandeep)
• Streaming hardness of Unique Games, APPROX 2019. (With R. Tao)
• Constructions of maximally recoverable local reconstruction codes via function fields. ICALP 2019. (With L. Jin and C. Xing)
• Beating Fredman-Komlos for perfect k-hashing, ICALP 2019. (With A. Riazanov)
• Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization, ISIT 2019. (With H. Jiang)
• An exponential lower bound on the sub-packetization of MSR codes, STOC 2019. (With O. Alrabiah)
• Bridging between 0/1 and Linear Programming via Random Walks, STOC 2019. (With J. Brakensiek)
• CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, STOC 2019. (With J. Brakensiek and S. Gopi)
• Algorithmic Polarization for Hidden Markov Models, ITCS 2019. (With P. Nakkiran and M. Sudan)
• Secret sharing with binary shares, ITCS 2019. (With F. Lin, M. Cheraghchi, R. Safavi-Naini and H. Wang)
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs, SODA 2019. (With J. Brakensiek)
• Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities , SODA 2019. (With S. Gopi and S. Yekhanin)
• Approximability of p->q matrix norms: Generalized Krivine rounding and hypercontractive hardness, SODA 2019. (With V. Bhattiprolu, E. Lee, M. Ghosh, M. Tulsiani). This is a merged extended abstract containing results from the following two papers:
  • Approximating Operator Norms via Generalized Krivine Rounding, arXiv:1804.03644, 2018.
  • Inapproximability of Matrix p-to-q Norms, ECCC TR18-037, 2018.

  ---

  
  
• Polar codes with exponentially small error at finite block length, RANDOM 2018. (With J. Blasiok and M. Sudan)
• How long can optimal locally repairable codes be?, RANDOM 2018. (With C. Xing and C. Yuan)
• Explicit optimal-length locally repairable codes of distance 5, Allerton 2018. (With A. Beemer, R. Coatney, H. López, F. Piñero)
• Lossless dimension expanders via linearized polynomials and subspace designs, CCC 2018. (With N. Resch and C. Xing)
• General Strong Polarization, STOC 2018. (With J. Blasiok, P. Nakkiran, A. Rudra, and M. Sudan)
• epsilon-MSR Codes: Contacting Fewer Code Blocks for Exact Repair, ISIT 2018. (With S. Lokam and S. Vikneshwar)
• On the List-Decodability of Random Linear Rank-Metric Codes , ISIT 2018. (With N. Resch)
• Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy, SODA 2018. (With J. Brakensiek)
• Coding against deletions in oblivious and online models, SODA 2018. (With Ray Li)
• A family of dictatorship tests with perfect completeness for 2-to-2 Label Cover, ECCC Technical Report TR17-141, 2017. (With J. Brakensiek)

---



• Optimal rate list decoding over bounded alphabets using algebraic-geometric codes, Journal submission, 2017. (With C. Xing)
• MDS code constructions with small sub-packetization and near-optimal repair bandwidth, Journal submission, 2017. (With A. Rawat, I. Tamo, and K. Efremenko))
• Hardness of Rainbow Coloring Hypergraphs, FSTTCS 2017, to appear. (With R. Saket)
• Weak decoupling, polynomial folds, and approximate optimization over the sphere, FOCS 2017. (With V. Bhattiprolu, M. Ghosh, E. Lee, and M. Tulsiani)
• The quest for strong inapproximability results with perfect completeness, APPROX 2017 and ECCC TR17-080. (With J. Brakensiek)
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph, APPROX 2017. (With A. Velingker and S. Velusamy)
• Locality via partially lifted codes, RANDOM 2017. (With S. L. Frank-Fischer and M. Wootters)
• Efficiently decodable codes for the binary deletion channel, RANDOM 2017. (With Ray Li)
• Sum-of-squares certificates for maxima of random tensors on the sphere, RANDOM 2017. (With V. Bhattiprolu and E. Lee)
• Subspace designs based on algebraic function fields, ICALP 2017. (With C. Xing and C. Yuan)
• An improved bound on the zero-error list decoding capacity of the 4/3 channel, ISIT 2017. (With M. Dalai and J. Radhakrishnan)
• epsilon-MSR codes with small sub-packetization, ISIT 2017. (With A. Rawat, I. Tamo, and K. Efremenko)
• MDS codes with small sub-packetization and near-optimal repair bandwidth, SODA 2017. (With A. Rawat)

---



• Robust Fourier and Polynomial Curve Fitting, FOCS 2016. (With D. Zuckerman)
• Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes, ISIT 2016. (With Ray Li)
• New hardness results for graph and hypergraph colorings, CCC 2016. (With J. Brakensiek)
• Tight bounds for communication assisted agreement distillation, CCC 2016. (With J. Radhakrishnan)
• Repairing Reed-Solomon Codes, STOC 2016. (With M. Wootters)
• Efficient list decoding of punctured Reed-Muller codes, IEEE Trans. Info. Theory, 2017 (With L. Jin and C. Xing)
• An improved bound on the fraction of correctable deletions, SODA'16 and IEEE Trans. Info. Theory, 2017. (With B. Bukh and J. Håstad)
• Efficient low-redundancy codes for correcting multiple deletions, SODA 2016. (With J. Brakensiek and S. Zbarsky)
• Nearly optimal NP-hardness of Unique Coverage, SODA 2016. (With E. Lee)
• Simple proof of hardness of Feedback Vertex Set, Theory of Computing, 12(6), 2016, 1-11. (With E. Lee)

  ---

  
  
• Towards a characterization of approximation resistance of symmetric CSPs, APPROX 2015. (With Euiwoong Lee)
• Approximate hypergraph coloring under low-discrepancy and related promises, APPROX 2015. (With V. Bhattiprolu and E. Lee)
• Dimension expanders via rank condensers, RANDOM 2015. (With Michael Forbes)
• Inapproximability of H-Transversal/Packing, APPROX 2015. (With Euiwoong Lee).
• Deletion codes in the high-noise and high-rate regimes, RANDOM 2015. (With Carol Wang)
• An entropy sumset inequality and polynomial convergence to Shannon capacity for all alphabets, CCC 2015. (With A. Velingker)
• Communication with Imperfectly Shared Randomness. ITCS 2015. (With C. Canonne, R. Meka and M. Sudan)
• Strong inapproximability results on balanced rainbow-colorable hypergraphs, SODA 2015. (With Euiwoong Lee)
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime, SODA 2015. (With M. Sudan, A. Velingker, and C. Wang)
  

  ---

  
  
• (2+eps)-SAT is NP-hard, FOCS 2014. (With P. Austrin and J. Håstad).
• Explicit rank-metric codes list-decodable with optimal redundancy, RANDOM 2014. (With Carol Wang)
• Hitting sets for low-degree polynomials with optimal density, CCC 2014. (With C. Xing)
• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes, STOC 2014. (With P. Harsha, J. Håstad, S. Srinivasan, and G. Varma)
• Non-Malleable Coding Against Bit-wise and Split-State Tampering, TCC 2014. (With M. Cheraghchi)
• Capacity of Non-Malleable Codes, ITCS 2014. (With M. Cheraghchi)
• Complexity of approximating CSP with Balance/Hard constraints, ITCS 2014. (With E. Lee)
• Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs, arXiv:1312.3024. (With A. K. Sinop)
• Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets, SODA 2014. (With C. Xing)
  • Related version Optimal rate algebraic list decoding using narrow ray class fields.
  
  

  ---

  
  
• Polar Codes: Speed of polarization and polynomial gap to capacity, FOCS 2013. (With P. Xia)
• PCPs via low-degree long code and hardness for constrained hypergraph coloring, FOCS 2013. (With I. Dinur)
• Explicit subspace designs, FOCS 2013. (With S. Kopparty)
• Combinatorial limitations of average-radius list decoding, RANDOM 2013. (With S. Narayanan)
• Superlinear lower bounds for multipass graph processing, CCC 2013. (With K. Onak)
• List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singeton bound, STOC 2013. (With C. Xing)
• Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs, ECCC TR13-071, 2013. (With S. Sachdeva and R. Saket)
• CopyCatch: Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks, WWW 2013. (With A. Beutel, W. Xu, C. Palow, and C. Faloutsos)
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes, SODA 2013. (With M. Cheraghchi and A. Velingker)
• Approximating Non-Uniform Sparsest Cut via Generalized Spectra, SODA 2013. (With A. K. Sinop)
• Linear-algebraic list decoding for variants of Reed-Solomon codes, IEEE Trans. Info. Theory, 59(6): 3257-3268, 2013. (With C. Wang)
  

  ---

  
  
• Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems, Manuscript, 2012. (With A. K. Sinop and Y. Zhou)
• Faster SDP hierarchy solvers for local rounding algorithms, FOCS 2012. (With A. K. Sinop.)
• Approximating bounded occurrence ordering CSPs, APPROX 2012. (With Y. Zhou)
• Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding, STOC 2012. (With C. Xing)
• List decoding subspace codes from insertions and deletions, ITCS 2012. (With S. Narayanan and C. Wang)
• Optimal column-based low-rank matrix reconstruction, SODA 2012. (With A. K. Sinop)
• Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph, SODA 2012. (With A. Bhaskara, M. Charikar, A. Vijayaraghavan, and Y. Zhou)
• Bypassing UGC from some optimal geometric inapproximability results, SODA 2012. (With P. Raghavendra, R. Saket, and Y. Wu)
  

  ---

  
  
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives, FOCS 2011. (With A. K. Sinop)
• Optimal rate list decoding via derivative codes, RANDOM 2011. (With C. Wang)
• Linear-algebraic list decoding of folded Reed-Solomon codes, CCC 2011.
• Finding almost-perfect graph bisections, ICS 2011. (With Y. Makarychev, P. Raghavendra, D. Steurer, and Y. Zhou)
• Beating the random ordering is hard: Every ordering CSP is approximation resistant, SIAM J. Computing, 2011. (With J. Håstad, R. Manokaran, P. Raghavendra, and M. Charikar)
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number, SODA 2011. (With A. K. Sinop)
• Tight Inapproximability Bounds for Almost-satisfiable Horn SAT and Exact Hitting Set, SODA 2011. (With Y. Zhou)
  

  ---

  
  
• Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, FOCS 2010. (With A. Smith)
• Bridging Shannon and Hamming: List Error-Correction with Optimal Rate, ICM 2010 (invited survey)
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs, ICALP 2010. (With R. Saket)
• SDP gaps for 2-to-1 and other Label-Cover variants, ICALP 2010. (With S. Khot, R. O'Donnell, P. Popat, M. Tulsiani, and Y. Wu)
• On the List-Decodability of Random Linear Codes, STOC 2010. (With J. Håstad and S. Kopparty)

---



• Agnostic learning of monomials by halfspaces is hard, FOCS 2009. (With V. Feldman, P. Raghavendra, and Yi Wu)
• Improved inapproximability results for maximum k-colorable subgraph. APPROX 2009. (With A. K. Sinop)
• Every permutation CSP of arity 3 is approximation resistant, CCC 2009. (With M. Charikar and R. Manokaran)
• Locally Testable Codes Require Redundant Testers, CCC 2009. (With E. Ben-Sasson, T. Kaufman, M. Sudan, and M. Viderman)
• Error Correction Up to the Information-Theoretic Limit. html version; More colorful digital edition. Communications of the ACM, March 2009. (With A. Rudra)
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate, Algebra and Number Theory, Vol. 4 (2010), No. 4, 433-463.
  • Extended abstract titled "Artin automorphisms, cyclotomic function fields, and folded list-decodable codes" appeared in STOC 2009.
    Here is an arXiv version.
• List decoding tensor products and interleaved codes. Extended asbtract in STOC 2009. (With P. Gopalan and P. Raghavendra)
• Max-Min allocation via degree lower-bounded arborescences, Proceedings of STOC 2009. (With M. H. Bateni and M. Charikar)
• Draft full version

---



• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph, FOCS 2008. (With R. Manokaran and P. Raghavendra)
• Euclidean sections with sublinear randomness and error-correction over the reals, RANDOM 2008. (with J. Lee and A. Wigderson)
• Constraint Satisfaction over a Non-Boolean domain: Approximation algorithms and Unique Games hardness, APPROX 2008. Also ECCC Report TR08-08. (With P. Raghavendra)
• Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction, ISIT 2008. (With W. Machmouchi)
• Soft decoding, dual BCH codes, and better eps-biased list-decodable codes, IEEE Trans. Info. Theory, 2010. Conference version CCC 2008. (With A. Rudra)
• Hardness amplification within NP against deterministic algorithms, J. Computer and System Sciences, special issue for Karp's Kyoto Prize. (With P. Gopalan)
  • Conference version in CCC 2008.
• Concatenated codes can achieve list decoding capacity, SODA 2008. Journal version in IEEE Trans. Info. Theory. (With A. Rudra)
• Almost Euclidean sections of L_1^N via expander codes, Accepted to Combinatorica, 2009. Conf. version in SODA 2008. (With J. Lee and A. Razborov)

---



• Inaproximability of edge-disjoint paths and low congestion routing on undirected graphs , Combinatorica. (With M. Andrews, J. Chuzhoy, S. Khanna, K. Talwar, and L. Zhang)
• Better binary list-decodable codes via multilevel concatenation, RANDOM 2007; Journal version in IEEE Trans. Info. Theory. (With A. Rudra)
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, Journal of the ACM, 56(4), 2009. (With C. Umans and S. Vadhan)
  • Originally Extractors and Condensers from Univariate Polynomials, ECCC Report TR06-134.
  • Conference version: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, CCC'07 (received the best paper award).
• Hardness of solving sparse overdetermined linear systems: A 3-query PCP over integers, ACM Transactions on Computation Theory, 1(2): (2009). Conference version in STOC 2007. (With P. Raghavendra)
• Hardness of routing with congestion in directed graphs, STOC 2007. (With J. Chuzhoy, S. Khanna, and K. Talwar)
  Earlier version: Hardness of low congestion routing in directed graphs, ECCC Report TR06-141. (With K. Talwar)

---



• Iterative Decoding of Low-Density Parity Check Codes, (A Survey), Issue 90 of Bulletin of the EATCS.
• Achieving list decoding capacity using folded Reed-Solomon codes, Invited paper at Allerton 2006. (With A. Rudra)
• Hardness of learning halfspaces with noise, Invited to SIAM J. Computing; Preliminary version in FOCS 2006. (With P. Raghavendra)
• Correlated Algebraic-Geometric Codes: Improved list decoding over bounded alphabets, Mathematics of Computation, 77(2008), 447-473. Extended abstract appeared in FOCS 2006. (With A. Patthak)
• On 2-Query Codeword Testing with Near-Perfect Completeness, ISAAC 2006.
• Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy, IEEE Trans. on Info. Theory, 54(1), Jan 2008. (With A. Rudra)
  • Originally Explicit Capacity-Achieving List-Decodable Codes, STOC 2006. (With A. Rudra)
• Algebraic-geometric generalizations of the Parvaresh-Vardy codes, ECCC Report TR05-132 (Subsumed by correlated AG codes paper above)
• List Decoding in Average-Case Complexity and Pseudorandomness. Invited mini-survey, ITW 2006.
• Hardness Amplification via Space-Efficient Direct Products, Computational Complexity. (With V. Kabanets)
• Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006, Invited to Algorithmica. (With P. Gopalan and R. Lipton)
• Correlation Clustering with a fixed number of clusters, Theory of Computing, 2(13) (2006). Conference version in SODA 2006. (With I. Giotis)

Surveys

• Bridging Shannon and Hamming: List Error-Correction with Optimal Rate, Proceedings of ICM 2010 (invited survey), Aug 2010.
• Error Correction Up to the Information-Theoretic Limit. html version; More colorful digital edition. Communications of the ACM, March 2009. (With A. Rudra)
• List decoding of binary codes, Brief survey, 2009.
  
• Iterative Decoding of Low-Density Parity Check Codes, Issue 90 of Bulletin of the EATCS.
  
• List decoding and pseudorandom constructions, AAECC 2007.
  
• Algorithmic Results in List Decoding, Foundations and Trends® in Theoretical Computer Science, Volume 2, Issue 2, 2007.
  
• List Decoding in Average-Case Complexity and Pseudorandomness. Mini-survey, ITW 2006.
• Error-correcting codes and Expander graphs SIGACT News, 35(3): 25-41, September 2004.
  
• Reflections on "Improved Decoding of Reed-Solomon and Algebraic-geometric Codes" IEEE Information Theory Newsletter, 2002. (With M. Sudan)
  
• Rapidly Mixing Markov Chains: A Comparison of Techniques, Unpublished, 2000.
  
• Evidence for a flat, accelerating Universe and the $\Lambda$CDM Model, Unpublished, 2000.
  

Coding Theory

(see above for papers 2006 onwards)

• V. Guruswami and S. Vadhan.
  A lower bound on list size for List Decoding
  Proceedings of RANDOM 2005.
  
  
• V. Guruswami and A. Rudra.
  Tolerant Locally Testable Codes
  Proceedings of RANDOM 2005.
  
  
• V. Guruswami and A. Rudra.
  Limits to List Decoding Reed-Solomon Codes
  IEEE Trans. Info. Theory, Aug 2006. Preliminary version in STOC 2005.
  
  
• V. Guruswami and A. Vardy.
  Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard
  IEEE Transactions on Information Theory 51(7): 2249-2256 (2005).
  Conference version in SODA 2005.
  
  
• V. Guruswami.
  Error-correcting codes and Expander graphs
  SIGACT News, 35(3): 25-41, September 2004.
  
  
• V. Guruswami and P. Indyk.
  Linear time list decoding in error-free settings
  Proceedings of ICALP 2004.
  
  
• V. Guruswami, D. Micciancio, and O. Regev.
  The Complexity of the Covering Radius Problem on Lattices and Codes
  Computational Complexity, 14(2):90-121, 2005.
  Preliminary version in Conference on Computational Complexity (CCC), 2004. 
  
  
• Venkatesan Guruswami.
  Better Extractors for Better Codes?
  Proceedings of STOC 2004.
  
  
• Venkatesan Guruswami and Piotr Indyk.
  Efficiently Decodable Codes meeting Gilbert-Varshamov bound for Low Rates
  Proceedings of SODA 2004.
  
  
• Venkatesan Guruswami.
  List Decoding with Side Information
  Proceedings of Complexity 2003.
  
  
• Venkatesan Guruswami and Piotr Indyk.
  Linear time encodable and list decodable codes
  Proceedings of STOC 2003.
  
  
• Venkatesan Guruswami and Igor Shparlinski.
  Unconditional Proof of Tightness of Johnson Bound
  Proceedings of SODA 2003.
  
  
• V. Guruswami.
  Limits to list decodability of linear codes
  Proceedings of STOC 2002.
  
  
• V. Guruswami and P. Indyk.
  Linear time encodable/decodable codes with near-optimal rate
  IEEE Trans. on Info. Theory, Oct. 2005.
  
  
• V. Guruswami and P. Indyk.
  Near-optimal linear time codes for unique decoding and new list decodable codes over smaller alphabets
  Proceedings of STOC 2002.
  
  
• Noga Alon, Venkatesan Guruswami, Tali Kaufman, and Madhu Sudan.
  Guessing secrets efficiently via list decoding
  Proceedings of SODA 2002. Appeared in special issue of ACM Transactions on Algorithms for SODA'02 papers.
  
  
• V. Guruswami and P. Indyk.
  Linear time codes to correct a maximum possible fraction of errors .
  Invited to Allerton 2001.
  
  
• Venkatesan Guruswami and Madhu Sudan.
  Decoding concatenated codes using soft information
  Proceedings of Complexity 2002.
  
  
• V. Guruswami and Madhu Sudan.
  Reflections on "Improved Decoding of Reed-Solomon and Algebraic-geometric Codes"
  IEEE Information Theory Newsletter, March 2002.
  
  
• V. Guruswami and P. Indyk.
  Expander-based Constructions of Efficiently Decodable Codes
  Proceedings of FOCS 2001.
  
  
• V. Guruswami.
  List Decoding from Erasures: Bounds and Code Constructions
  IEEE Trans. on Info. Theory, November 2003.
  
  
• V. Guruswami.
  Constructions of Codes from Number Fields
  IEEE Trans. on Info. Theory, 2003.
  (Here is a 2 page summary.)
  
  
• V. Guruswami.
  List Decoding of Error-Correcting Codes
  Ph.D thesis, MIT, August 2001.
  
  
• V. Guruswami and M. Sudan.
  Extensions to the Johnson Bound
  Manuscript, February 2001.
  
  
• V. Guruswami, J. Håstad, M. Sudan and D. Zuckerman.
  Combinatorial Bounds for List Decoding
  IEEE Trans. on Information Theory, May 2002.
  Preliminary version invited to the 38th Annual Allerton Conference on Communication, Control and Computing.
  
  
• V. Guruswami, A. Sahai and M. Sudan.
  Soft-decision Decoding of Chinese Remainder Codes
  Proceedings of FOCS 2000.
  
  
• V. Guruswami and Madhu Sudan.
  On Representations of Algebraic-Geometric Codes for List Decoding
  IEEE Transactions on Information Theory, May 2001.
  
  
• V. Guruswami and M. Sudan.
  List decoding algorithms for certain concatenated codes
  Proceedings of STOC 2000.
  
  
• Venkatesan Guruswami and Madhu Sudan.
  Improved Decoding of Reed-Solomon and Algebraic-Geometric codes
  IEEE Transactions on Information Theory, 45 (1999), pp. 1757-1767.
  
  

Approximation Algorithms, Hardness of Approximations, PCPs

(see above for papers 2006 onwards)

• V. Guruswami and L. Trevisan.
  The Complexity of Making Unique Choices: Approximating 1-in-kSAT
  Proceedings of APPROX 2005.
  
  
• V. Guruswami and S. Khot.
  Hardness of Max 3SAT with no mixed clauses
  Proceedings of CCC 2005.
  
  
• V. Guruswami, J. D. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry.
  On Profit-Maximizing Envy-free Pricing
  Proceedings of SODA 2005.
  
  
• V. Guruswami, D. Micciancio, and O. Regev.
  The Complexity of the Covering Radius Problem on Lattices and Codes
  Proceedings of CCC 2004; Journal version in special issue of Computational Complexity.
  
  
• Moses Charikar, Venkatesan Guruswami, and Anthony Wirth.
  Clustering with Qualitative Information
  JCSS, October 2005 (Special issue). Preliminary version in FOCS 2003.
  
  
• I. Dinur, V. Guruswami, S. Khot and O. Regev.
  A new multilayered PCP and the hardness of hypergraph vertex cover
  SIAM J. Comput. 34(5): 1129-1146 (2005)
  Conference version in STOC 2003.
  
  
• I. Dinur, V. Guruswami and S. Khot.
  Vertex Cover on k-uniform hypergraphs is hard to approximate within factor (k-3-eps)
  ECCC Technical Report TR02-027.
  
  
• V. Guruswami and P. Indyk.
  Embeddings and non-approximability of geometric problems
  Proceedings of SODA 2003.
  
  
• L. Engebretsen and V. Guruswami.
  Is Constraint Satisfaction over two variables always easy?
  Random Structures and Algorithms, 2004..Preliminary version in Proc. of  RANDOM 2002.
  
  
• V. Guruswami, J. Hastad and M. Sudan.
  Hardness of Approximate Hypergraph Coloring
  SIAM J. Comput. 31(6): 1663-1686 (2002)
  Preliminary version appeared in FOCS 2000 (the journal version is a significant revision).
  
  
• M. Charikar, V. Guruswami, R. Kumar, S. Rajagopalan and A. Sahai.
  Combinatorial Feature Selection Problems
  Proc. of FOCS 2000.
  
  
• V. Guruswami and S. Khanna
  On the hardness of 4-coloring a 3-colorable graph
  SIAM J. Disc. Math, 2004. (Preliminary version in Proc. of Complexity 2000, pp. 188-197.)
  
  
• V. Guruswami.
  Inapproximability results for Set Splitting and Satisfiability Problems with no mixed clauses
  Algorithmica, 2003 (Special issue for selected papers from APPROX 2000.)
  
  
• V. Guruswami, S. Khanna, R. Rajaraman, F.B. Shepherd, M. Yannakakis.
  Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
  JCSS, 67(3):473-496, 2003. (Preliminary version in Proc. of STOC 1999.)
  
  
• Yevgeniy Dodis, Venkatesan Guruswami and Sanjeev Khanna
  The 2-Catalog Segmentation Problem
  Proceedings of SODA 1999.
  
  
• Venkatesan Guruswami, Daniel Lewin, Madhu Sudan and Luca Trevisan
  A tight characterization of NP with 3 query PCPs
  Proceedings of FOCS 1998. Also available as ECCC Technical Report TR98-034.
  [The technical content of this paper (even the ECCC version) is somewhat difficult to read without familiarity with Hastad's paper. A more self-contained version can be found below in the form of my Master's thesis.]
  
  
• V. Guruswami.
  Query-efficient Checking of Proofs and Improved PCP Characterizations of NP
  Master's Thesis, MIT, May 1999. Here is an HTML abstract.
  
  
• V. Guruswami and C. Pandu Rangan.
  A natural family of Optimization Problems with arbitrarily small approximation thresholds
  Information Processing Letters, 68 (1998), pp. 241-248.
  
  
• V. Guruswami and C.Pandu Rangan.
  Approximate Triclique Coloring for Register Allocation
  Information Processing Letters, Vol. 60, 1996.
  
  

Other Theory Papers

• M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan and A. Sahai.
  Query Strategies for Priced Information
  JCSS 64(4):785-819, 2002. (Preliminary version in Proc. of STOC 2000.)
  
  
• V. Guruswami and A. Sahai.
  Multiclass Learning, Boosting, and Error-correcting codes
  Proceedings of COLT'99.
  
  

Theses

• List Decoding of Error-Correcting Codes, Ph.D. dissertation, MIT, 2001.
  
  
• Query-efficient Checking of Proofs and Improved PCP Characterizations of NP, Master's thesis, MIT, May 1999.
  Here is an HTML abstract of the thesis.
  
  
• Intractability Results for Certain Graph-theoretic Optimization and Approximation Problems, Senior Thesis, Indian Institute of Technology, Madras, May 1997.

Algorithmic and Structural Graph Theory

• V. Guruswami. Enumerative Aspects of certain classes of Perfect Graphs, Discrete Mathematics, 205 (1999), pp. 97-117.
  
  
• V. Guruswami, U.Rotics, M.S.Madanlal, J.A.Makowsky and C.Pandu Rangan, Restrictions of Minimum Spanner Problems, Information and Computation, August 97.
  
  
• V. Guruswami and C. Pandu Rangan. Algorithmic aspects of clique-transversal and clique-independent sets, Discrete Applied Mathematics, 100 (2000), pp. 183-202.
  
  
• V. Guruswami. Maximum Cut on line and total graphs, Discrete Applied Mathematics, 92 (1999), pp. 217-221.
  
  
• V. Guruswami, C. Pandu Rangan, M.S. Chang, G.J. Chang and C.K. Wong, The Vertex-disjoint Triangles Problem, Proceedings of WG'98, Smolenice Castle, Slovakia, June 1998. Journal version in Computing.
  
  
• V. Guruswami and C. Pandu Rangan. The Complexity of Graph Packing Problems. Unpublished Manuscript.
  
  
• V. Guruswami and C. Pandu Rangan. Algorithmic aspects of Edge Dominating sets. Unpublished Manuscript.
  
  
• V. Guruswami, G. Mohan and C. Siva Rama Murthy, Probabilistic Routing on Wavelength-routed Multistage, Hypercube and Debruijn Networks, Proc. of the Fourth International Conference on High Performance Computing (HiPC '97).
  
  
• M.S.Madanlal, V. Guruswami and C.Pandu Rangan, Tree 3-spanners on Interval, Permutation and Regular Bipartite graphs, Information Processing Letters, Vol. 59, 1996.
  
  
• [Undergraduate Thesis] Intractability Results for Certain Graph-theoretic Optimization and Approximation Problems, Indian Institute of Technology, Madras, May 1997.