Publications - Venkatesan Guruswami

JournalSIAM J. Comput. 52(1) 132-155 (2023)
ConferenceSODA 2019: 1358-1368; conference title: Approximability of p to q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

2018

#172

Polar codes with exponentially small error at finite block length

Jaroslaw Blasiok, V.G., Madhu Sudan

ConferenceAPPROX-RANDOM 2018: 34:1-34:17

#171

How Long Can Optimal Locally Repairable Codes Be?

V.G., Chaoping Xing, Chen Yuan

JournalIEEE Trans. Inf. Theory 65(6) 3662-3670 (2019)
ConferenceAPPROX-RANDOM 2018: 41:1-41:11

#170

Explicit optimal-length locally repairable codes of distance 5

Allison Beemer, Ryan Coatney, V.G., Hiram H. Lopez, Fernando Piñero

ConferenceAllerton 2018: 800-804

#169

Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs

V.G., Nicolas Resch, Chaoping Xing

JournalCombinatorica 41(4) 545-579 (2021)
ConferenceCCC 2018: 4:1-4:16

#168

General Strong Polarization

Jaroslaw Blasiok, V.G., Preetum Nakkiran, Atri Rudra, Madhu Sudan

JournalJ. ACM 69(2) 11:1-11:67 (2022)
ConferenceSTOC 2018: 485-492

#167

ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair

V.G., Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman

JournalIEEE Trans. Inf. Theory 66(11) 6749-6761 (2020)
ConferenceISIT 2018: 2371-2375

#166

On the List-Decodability of Random Linear Rank-Metric Codes

V.G., Nicolas Resch

ConferenceISIT 2018: 1505-1509

#165

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Joshua Brakensiek, V.G.

JournalSIAM J. Comput. 50(6) 1663-1700 (2021)
ConferenceSODA 2018: 1782-1801; conference title: Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy

#164

Coding Against Deletions in Oblivious and Online Models

V.G., Ray Li

JournalIEEE Trans. Inf. Theory 66(4) 2352-2374 (2020)
ConferenceSODA 2018: 625-643

#163

A family of dictatorship tests with perfect completeness for 2-to-2 Label Cover

Joshua Brakensiek, V.G.

JournalChicago Journal of Theoretical Computer Science 2023(2)
ManuscriptECCC Technical Report TR17-141, 2017

2017

#162

MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth

Ankit Singh Rawat, Itzhak Tamo, V.G., Klim Efremenko

JournalIEEE Trans. Inf. Theory 64(10) 6506-6525 (2018)
ConferenceSODA 2017: 2109-2122

#161

Hardness of Rainbow Coloring Hypergraphs

V.G., Rishi Saket

ConferenceFSTTCS 2017: 33:33-33:15

#160

Weak decoupling, polynomial folds, and approximate optimization over the sphere

Vijay Bhattiprolu, Mrinalkanti Ghosh, V.G., Euiwoong Lee, Madhur Tulsiani

ConferenceFOCS 2017: 1008-1019

#159

The Quest for Strong Inapproximability Results with Perfect Completeness

Joshua Brakensiek, V.G.

JournalACM Trans. Algorithms 17(3) 27:1-27:35 (2021)
ConferenceAPPROX-RANDOM 2017: 4:1-4:20

#158

Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph

V.G., Ameya Velingker, Santhoshini Velusamy

ConferenceAPPROX-RANDOM 2017: 8:1-8:19

#157

Locality via partially lifted codes

S. Luna Frank-Fischer, V.G., Mary Wootters

ConferenceAPPROX-RANDOM 2017: 43:1-43:17

#156

Polynomial Time Decodable Codes for the Binary Deletion Channel

V.G., Ray Li

JournalIEEE Trans. Inf. Theory 65(4) 2171-2178 (2019)
ConferenceAPPROX-RANDOM 2017: 47:1-47:13

#155

Sum-of-squares certificates for maxima of random tensors on the sphere

Vijay Bhattiprolu, V.G., Euiwoong Lee

ConferenceAPPROX-RANDOM 2017: 31:1-31:20

#154

Subspace designs based on algebraic function fields

V.G., Chaoping Xing, Chen Yuan

JournalTrans. Amer. Math. Soc. 370(12) 8757-8775 (2018)
ConferenceICALP 2017: 86:1-86:10

#153

An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel

Marco Dalai, V.G., Jaikumar Radhakrishnan

JournalIEEE Trans. Inf. Theory 66(2) 749-756 (2020)
ConferenceISIT 2017: 1658-1662

#152

epsilon-MSR codes with small sub-packetization

Ankit Singh Rawat, Itzhak Tamo, V.G., Klim Efremenko

ConferenceISIT 2017: 2043-2047

#151

MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth

Ankit Singh Rawat, Itzhak Tamo, V.G., Klim Efremenko

JournalIEEE Trans. Inf. Theory 64(10) 6506-6525 (2018)
ConferenceSODA 2017: 2109-2122

2016

#150

Robust Fourier and Polynomial Curve Fitting

V.G., David Zuckerman

ConferenceFOCS 2016: 751-759

#149

Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes

V.G., Ray Li

ConferenceISIT 2016: 620-624

#148

New hardness results for graph and hypergraph colorings

Joshua Brakensiek, V.G.

ConferenceCCC 2016: 14:1-14:27

#147

Tight bounds for communication assisted agreement distillation

V.G., Jaikumar Radhakrishnan

ConferenceCCC 2016: 6:1-6:17

#146

Repairing Reed-Solomon Codes

V.G., Mary Wootters

JournalIEEE Trans. Inf. Theory 63(9) 5684-5698 (2017)
ConferenceSTOC 2016: 216-226

#145

Efficiently List-Decodable Punctured Reed-Muller Codes

V.G., Lingfei Jin, Chaoping Xing

JournalIEEE Trans. Inf. Theory 63(7) 4317-4324 (2017)

#144

An Improved Bound on the Fraction of Correctable Deletions

Boris Bukh, V.G., Johan Håstad

JournalIEEE Trans. Inf. Theory 63(1) 93-103 (2017)
ConferenceSODA 2016: 1893-1901

#143

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Joshua Brakensiek, V.G., Samuel Zbarsky

JournalIEEE Trans. Inf. Theory 64(5) 3403-3410 (2018)
ConferenceSODA 2016: 1884-1892

#142

Nearly Optimal NP-Hardness of Unique Coverage

V.G., Euiwoong Lee

JournalSIAM J. Comput. 46(3) 1018-1028 (2017)
ConferenceSODA 2016: 1724-1730

#141

Simple Proof of Hardness of Feedback Vertex Set

V.G., Euiwoong Lee

JournalTheory Comput. 12(1) 1-11 (2016)

2015

#140

Towards a Characterization of Approximation Resistance for Symmetric CSPs

V.G., Euiwoong Lee

JournalTheory Comput. 13(1) 1-24 (2017)
ConferenceAPPROX-RANDOM 2015: 305-322

#139

Approximate hypergraph coloring under low-discrepancy and related promises

Vijay V. S. P. Bhattiprolu, V.G., Euiwoong Lee

ConferenceAPPROX-RANDOM 2015: 152-174

#138

Dimension expanders via rank condensers

Michael A. Forbes, V.G.

ConferenceAPPROX-RANDOM 2015: 800-814

#137

Inapproximability of H-Transversal/Packing

V.G., Euiwoong Lee

JournalSIAM J. Discret. Math. 31(3) 1552-1571 (2017)
ConferenceAPPROX-RANDOM 2015: 284-304

#136

Deletion Codes in the High-Noise and High-Rate Regimes

V.G., Carol Wang

JournalIEEE Trans. Inf. Theory 63(4) 1961-1970 (2017)
ConferenceAPPROX-RANDOM 2015: 867-880

#135

An entropy sumset inequality and polynomial convergence to Shannon capacity for all alphabets

V.G., Ameya Velingker

ConferenceCCC 2015: 42-57

#134

Communication With Imperfectly Shared Randomness

Clément L. Canonne, V.G., Raghu Meka, Madhu Sudan

JournalIEEE Trans. Inf. Theory 63(10) 6799-6818 (2017)
ConferenceITCS 2015: 257-262

#133

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

V.G., Euiwoong Lee

JournalComb. 38(3) 547-599 (2018)
ConferenceSODA 2015: 822-836

#132

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

V.G., Madhu Sudan, Ameya Velingker, Carol Wang

ConferenceSODA 2015: 1312-1325

2014

#131

(2+ε)-Sat Is NP-hard

Per Austrin, V.G., Johan Håstad

JournalSIAM J. Comput. 46(5) 1554-1573 (2017)
ConferenceFOCS 2014: 1-10

#130

Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs

V.G., Carol Wang, Chaoping Xing

JournalIEEE Trans. Inf. Theory 62(5) 2707-2718 (2016)

#129

Hitting sets for low-degree polynomials with optimal density

V.G., Chaoping Xing

ConferenceCCC 2014: 161-168

#128

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes

V.G., Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

JournalSIAM J. Comput. 46(1) 132-159 (2017)
ConferenceSTOC 2014: 614-623

#127

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Mahdi Cheraghchi, V.G.

JournalJ. Cryptol. 30(1) 191-241 (2017)
ConferenceTCC 2014: 440-464

#126

Capacity of Non-Malleable Codes

Mahdi Cheraghchi, V.G.

JournalIEEE Trans. Inf. Theory 62(3) 1097-1118 (2016)
ConferenceITCS 2014: 155-168

#125

Complexity of Approximating CSP with Balance / Hard Constraints

V.G., Euiwoong Lee

JournalTheory Comput. Syst. 59(1) 76-98 (2016)
ConferenceITCS 2014: 439-448

#124

Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs

V.G., Ali Kemal Sinop

ManuscriptarXiv:1312.3024

#123

Optimal rate algebraic list decoding using narrow ray class fields

V.G., Chaoping Xing

JournalJ. Comb. Theory A 129 160-183 (2015)
ConferenceSODA 2014: 1858-1866

2013

#122

Polar Codes: Speed of Polarization and Polynomial Gap to Capacity

V.G., Patrick Xia

JournalIEEE Trans. Inf. Theory 61(1) 3-16 (2015)
ConferenceFOCS 2013: 310-319

#121

PCPs via low-degree long code and hardness for constrained hypergraph coloring

Irit Dinur, V.G.

JournalIsrael J. Math. 209(2) 611-649 (2015)
ConferenceFOCS 2013: 340-349

#120

Explicit subspace designs

V.G., Swastik Kopparty

JournalCombinatorica 36(2) 161-185 (2016)
ConferenceFOCS 2013: 608-617

#119

Combinatorial Limitations of Average-Radius List-Decoding

V.G., Srivatsan Narayanan

JournalIEEE Trans. Inf. Theory 60(10) 5827-5842 (2014)
ConferenceAPPROX-RANDOM 2013: 591-606

#118

Superlinear Lower Bounds for Multipass Graph Processing

V.G., Krzysztof Onak

JournalAlgorithmica 76(3) 654-683 (2016)
ConferenceCCC 2013: 287-298

#117

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

V.G., Chaoping Xing

JournalJournal version appears as part of merged and expanded J. ACM 69(2) 10:1-10:48 (2022)
ConferenceSTOC 2013: 843-852

#116

Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs

V.G., Sushant Sachdeva, Rishi Saket

JournalSIAM J. Discret. Math. 29(1) 36-58 (2015)

#115

CopyCatch: Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks

Alex Beutel, Wanhong Xu, V.G., Christopher Palow, Christos Faloutsos

ConferenceWWW 2013: 119-130

#114

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

Mahdi Cheraghchi, V.G., Ameya Velingker

JournalSIAM J. Comput. 42(5) 1888-1914 (2013)
ConferenceSODA 2013: 432-442

#113

Approximating Non-Uniform Sparsest Cut via Generalized Spectra

V.G., Ali Kemal Sinop

ConferenceSODA 2013: 295-305

#112

Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes

V.G., Carol Wang

JournalIEEE Trans. Inf. Theory 59(6) 3257-3268 (2013)

2012

#111

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

V.G., Ali Kemal Sinop, Yuan Zhou

JournalSIAM J. Optim. 24(4) 1698-1717 (2014)

#110

Faster SDP hierarchy solvers for local rounding algorithms

V.G., Ali Kemal Sinop

ConferenceFOCS 2012: 197-206

#109

Approximating bounded occurrence ordering CSPs

V.G., Yuan Zhou

ConferenceAPPROX-RANDOM 2012: 158-169

#108

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

V.G., Chaoping Xing

JournalJournal version appears as part of merged and expanded J. ACM 69(2) 10:1-10:48 (2022)
ConferenceSTOC 2012: 339-350

#107

List decoding subspace codes from insertions and deletions

V.G., Srivatsan Narayanan, Carol Wang

ConferenceITCS 2012: 183-189

#106

Optimal column-based low-rank matrix reconstruction

V.G., Ali Kemal Sinop

ConferenceSODA 2012: 1207-1214

#105

Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, V.G., Yuan Zhou

ConferenceSODA 2012: 388-405

#104

Bypassing UGC from Some Optimal Geometric Inapproximability Results

V.G., Prasad Raghavendra, Rishi Saket, Yi Wu

JournalACM Trans. Algorithms 12(1) 6:1-6:25 (2016)
ConferenceSODA 2012: 699-717

2011

#103

The query complexity of estimating weighted averages

Amit Chakrabarti, V.G., Andrew Wirth, Anthony Wirth

JournalActa Informatica 48(7-8) 417-426 (2011)

#102

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

V.G., Ali Kemal Sinop

ConferenceFOCS 2011

#101

Optimal rate list decoding via derivative codes

V.G., Carol Wang

ConferenceAPPROX-RANDOM 2011: 593-604

#100

Linear-algebraic list decoding of folded Reed-Solomon codes

V.G.

ConferenceCCC 2011: 77-85

#99

Finding almost-perfect graph bisections

V.G., Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou

ConferenceICS 2011

#98

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

V.G., Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

JournalSIAM J. Comput. 40(3) 878-914 (2011)

#97

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

V.G., Ali Kemal Sinop

ConferenceSODA 2011: 1615-1626

#96

Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set

V.G., Yuan Zhou

JournalTheory Comput. 8(1) 239-267 (2012)
ConferenceSODA 2011: 1574-1589

2010

#95

Optimal Rate Code Constructions for Computationally Simple Channels

V.G., Adam D. Smith

JournalJ. ACM 63(4) 35:1-35:37 (2016)
ConferenceFOCS 2010: 723-732

#94

Bridging Shannon and Hamming: List Error-Correction with Optimal Rate

V.G.

ConferenceICM 2010 invited survey

#93

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs

V.G., Rishi Saket

ConferenceICALP (1) 2010: 360-371

#92

SDP gaps for 2-to-1 and other Label-Cover variants

V.G., Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu

ConferenceICALP (1) 2010: 617-628

#91

On the List-Decodability of Random Linear Codes

V.G., Johan Håstad, Swastik Kopparty

JournalIEEE Trans. Inf. Theory 57(2) 718-725 (2011)
ConferenceSTOC 2010: 409-416

2009

#90

Agnostic Learning of Monomials by Halfspaces Is Hard

Vitaly Feldman, V.G., Prasad Raghavendra, Yi Wu

JournalSIAM J. Comput. 41(6) 1558-1590 (2012)
ConferenceFOCS 2009: 385-394

#89

Improved Inapproximability Results for Maximum k-Colorable Subgraph

V.G., Ali Kemal Sinop

JournalTheory Comput. 9 413-435 (2013)
ConferenceAPPROX-RANDOM 2009: 163-176

#88

Every permutation CSP of arity 3 is approximation resistant

Moses Charikar, V.G., Rajsekar Manokaran

ConferenceCCC 2009: 62-73

#87

Locally Testable Codes Require Redundant Testers

Eli Ben-Sasson, V.G., Tali Kaufman, Madhu Sudan, Michael Viderman

JournalSIAM J. Comput. 39(7) 3230-3247 (2010)
ConferenceCCC 2009: 52-61

#86

Error correction up to the information-theoretic limit

V.G., Atri Rudra

JournalCommun. ACM 52(3) 87-95 (2009)

#85

Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate

V.G.

JournalAlgebra Number Theory 4(4) 433-463 (2010)
ConferenceSTOC 2009: 23-32

#84

List Decoding Tensor Products and Interleaved Codes

Parikshit Gopalan, V.G., Prasad Raghavendra

JournalSIAM J. Comput. 40(5) 1432-1462 (2011)
ConferenceSTOC 2009: 13-22

#83

Max-Min allocation via degree lower-bounded arborescences

MohammadHossein Bateni, Moses Charikar, V.G.

ConferenceSTOC 2009: 543-552

2008

#82

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

V.G., Rajsekar Manokaran, Prasad Raghavendra

ConferenceFOCS 2008: 573-582

#81

Euclidean sections with sublinear randomness and error-correction over the reals

V.G., James R. Lee, Avi Wigderson

ConferenceAPPROX-RANDOM 2008: 444-454

#80

Constraint Satisfaction over a Non-Boolean domain: Approximation algorithms and Unique Games hardness

V.G., Prasad Raghavendra

ConferenceAPPROX-RANDOM 2008: 77-90
Manuscriptalso ECCC Report TR08-08

#79

Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction

V.G., Widad Machmouchi

ConferenceISIT 2008: 1968-1972

#78

Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes

V.G., Atri Rudra

JournalIEEE Trans. Inf. Theory 57(2) 705-717 (2011)
ConferenceCCC 2008: 163-174

#77

Hardness amplification within NP against deterministic algorithms

Parikshit Gopalan, V.G.

JournalJ. Comput. Syst. Sci. 77(1) 107-121 (2011)
ConferenceCCC 2008: 19-30

#76

The existence of concatenated codes list-decodable up to the hamming bound

V.G., Atri Rudra

JournalIEEE Trans. Inf. Theory 56(10) 5195-5206 (2010)

#75

Almost Euclidean subspaces of l 1N VIA expander codes

V.G., James R. Lee, Alexander A. Razborov

JournalComb. 30(1) 47-68 (2010)

2007

#74

Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs

Matthew Andrews, Julia Chuzhoy, V.G., Sanjeev Khanna, Kunal Talwar, Lisa Zhang

JournalComb. 30(5) 485-520 (2010)

#73

Better Binary List Decodable Codes Via Multilevel Concatenation

V.G., Atri Rudra

JournalIEEE Trans. Inf. Theory 55(1) 19-26 (2009)
ConferenceAPPROX-RANDOM 2007: 554-568

#72

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

V.G., Christopher Umans, Salil P. Vadhan

JournalJ. ACM 56(4) 20:1-20:34 (2009)
ConferenceCCC 2007: 96-108

#71

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers

V.G., Prasad Raghavendra

JournalACM Trans. Comput. Theory 1(2) 6:1-6:20 (2009)
ConferenceSTOC 2007: 198-206

#70

Hardness of routing with congestion in directed graphs

Julia Chuzhoy, V.G., Sanjeev Khanna, Kunal Talwar

ConferenceSTOC 2007: 165-178

2006

#69

Iterative Decoding of Low-Density Parity Check Codes

V.G.

JournalBull. EATCS 90 53-88 (2006)

#68

Achieving list decoding capacity using folded Reed-Solomon codes

V.G., Atri Rudra

Conferenceinvited paper at Allerton 2006

#67

Hardness of Learning Halfspaces with Noise

V.G., Prasad Raghavendra

JournalSIAM J. Comput. 39(2) 742-765 (2009)
ConferenceFOCS 2006: 543-552

#66

Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets

V.G., Anindya C. Patthak

JournalMath. Comput. 77(261) 447-473 (2008)
ConferenceFOCS 2006: 227-238

#65

On 2-Query Codeword Testing with Near-Perfect Completeness

V.G.

ConferenceISAAC 2006: 267-276

#64

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

V.G., Atri Rudra

JournalIEEE Trans. Inf. Theory 54(1) 135-150 (2008)
ConferenceSTOC 2006: 1-10

#63

Algebraic-geometric generalizations of the Parvaresh-Vardy codes

V.G.

ManuscriptECCC Report TR05-132, 2005
Publicationsubsumed by correlated AG codes paper

#62

List Decoding in Average-Case Complexity and Pseudorandomness

V.G.

ConferenceITW 2006: 32-36
Manuscriptinvited mini-survey, ITW 2006

#61

Hardness Amplification via Space-Efficient Direct Products

V.G., Valentine Kabanets

JournalComput. Complex. 17(4) 475-500 (2008)
ConferenceLATIN 2006: 556-568

#60

Algorithms for Modular Counting of Roots of Multivariate Polynomials

Parikshit Gopalan, V.G., Richard J. Lipton

JournalAlgorithmica 50(4) 479-496 (2008)
ConferenceLATIN 2006: 544-555

#59

Correlation Clustering with a Fixed Number of Clusters

Ioannis Giotis, V.G.

JournalTheory Comput. 2(13) 249-266 (2006)

2005

#58

List Decoding of Error-Correcting Codes. Lecture Notes in Computer Science, Vol. 3282, Springer-Verlag, 2005. 350 p

V.G.

ManuscriptPublication details forthcoming

#57

A Lower Bound on List Size for List Decoding

V.G., Salil P. Vadhan

JournalIEEE Trans. Inf. Theory 56(11) 5681-5688 (2010)
ConferenceAPPROX-RANDOM 2005: 318-329

#56

Tolerant Locally Testable Codes

V.G., Atri Rudra

ConferenceAPPROX-RANDOM 2005: 306-317

#55

Limits to List Decoding Reed-Solomon Codes

V.G., Atri Rudra

JournalIEEE Trans. Inf. Theory 52(8) 3642-3649 (2006)
ConferenceSTOC 2005: 602-609

#54

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

V.G., Alexander Vardy

JournalIEEE Trans. Inf. Theory 51(7) 2249-2256 (2005)

#53

The Complexity of Making Unique Choices: Approximating 1-in-kSAT

V.G., Luca Trevisan

ConferenceAPPROX-RANDOM 2005: 99-110

#52

Hardness of Max 3SAT with no mixed clauses

V.G., Subhash Khot

ConferenceCCC 2005: 154-162

#51

On Profit-Maximizing Envy-free Pricing

V.G., Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry

ConferenceSODA 2005

2004

#50

Error-correcting codes and Expander graphs, SIGACT News 35(3):25-41, September 2004

V.G.

JournalSIGACT News 35(3) 25-41 (2004)

#49

Linear time list decoding in error-free settings

V.G., Piotr Indyk

ConferenceICALP 2004: 695-707

#48

The complexity of the covering radius problem

V.G., Daniele Micciancio, Oded Regev

JournalComput. Complex. 14(2) 90-121 (2005)
ConferenceCCC 2004: 161-173

#47

Better Extractors for Better Codes?

V.G.

ConferenceSTOC 2004: 436-444

#46

Efficiently Decodable Codes meeting Gilbert-Varshamov bound for Low Rates

V.G., Piotr Indyk

ConferenceSODA 2004

2003

#45

List Decoding with Side Information

V.G.

ConferenceCCC 2003: 300-
ManuscriptPublication details forthcoming

#44

Linear time encodable and list decodable codes

V.G., Piotr Indyk

ConferenceSTOC 2003: 126-135

#43

Unconditional Proof of Tightness of Johnson Bound

V.G., Igor E. Shparlinski

ConferenceSODA 2003

#42

Clustering with qualitative information

Moses Charikar, V.G., Anthony Wirth

JournalJ. Comput. Syst. Sci. 71(3) 360-383 (2005)
ConferenceFOCS 2003: 524-533

#41

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Irit Dinur, V.G., Subhash Khot, Oded Regev

JournalSIAM J. Comput. 34(5) 1129-1146 (2005)
ConferenceSTOC 2003: 595-601

#40

Embeddings and non-approximability of geometric problems

V.G., Piotr Indyk

ConferenceSODA 2003

#39

Constructions of codes from number fields

V.G.

JournalIEEE Trans. Inf. Theory 49(3) 594-603 (2003)
ConferenceAAECC 2001: 129-140

#38

List decoding from erasures: bounds and code constructions

V.G.

JournalIEEE Trans. Inf. Theory 49(11) 2826-2833 (2003)
ConferenceFSTTCS 2001: 195-206

2002

#37

Limits to list decodability of linear codes

V.G.

ConferenceSTOC 2002: 802-811

#36

Linear-time encodable/decodable codes with near-optimal rate

V.G., Piotr Indyk

JournalIEEE Trans. Inf. Theory 51(10) 3393-3400 (2005)

#35

Near-optimal linear time codes for unique decoding and new list decodable codes over smaller alphabets

V.G., Piotr Indyk

ConferenceSTOC 2002: 812-821

#34

Guessing secrets efficiently via list decoding

Noga Alon, V.G., Tali Kaufman, Madhu Sudan

JournalACM Trans. Algorithms 3(4) 42 (2007)

#33

Decoding concatenated codes using soft information

V.G., Madhu Sudan

ConferenceCCC 2002: 148-157

#32

Reflections on "Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes"

V.G., Madhu Sudan

SurveyIEEE Information Theory Society Newsletter 52(1) 6-12 (March 2002)

#31

Hardness of Approximate Hypergraph Coloring

V.G., Johan Håstad, Madhu Sudan

JournalSIAM J. Comput. 31(6) 1663-1686 (2002)
ConferenceFOCS 2000: 149-158

#30

Is constraint satisfaction over two variables always easy?

Lars Engebretsen, V.G.

JournalRandom Struct. Algorithms 25(2) 150-178 (2004)
ConferenceRANDOM 2002: 224-238

#29

Query Strategies for Priced Information

Moses Charikar, Ronald Fagin, V.G., Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai

JournalJ. Comput. Syst. Sci. 64(4) 785-819 (2002)
ConferenceSTOC 2000: 582-591

2001

#28

The Kr-Packing Problem

V.G., C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong

JournalComputing 66(1) 79-89 (2001)

#27

Expander-based Constructions of Efficiently Decodable Codes

V.G., Piotr Indyk

ConferenceFOCS 2001: 658-667

#26

List Decoding of Error-Correcting Codes

V.G.

PublicationPh.D. thesis, MIT, August 2001

#25

Extensions to the Johnson Bound

V.G., Madhu Sudan

Manuscriptmanuscript, February 2001

#24

Combinatorial bounds for list decoding

V.G., Johan Håstad, Madhu Sudan, David Zuckerman

JournalIEEE Trans. Inf. Theory 48(5) 1021-1034 (2002)

#23

On representations of algebraic-geometry codes

V.G., Madhu Sudan

JournalIEEE Trans. Inf. Theory 47(4) 1610-1613 (2001)
ConferenceESA 2000: 244-255

2000

#22

Algorithmic aspects of clique-transversal and clique-independent sets

V.G., C. Pandu Rangan

JournalDiscret. Appl. Math. 100(3) 183-202 (2000)

#21

Soft-decision Decoding of Chinese Remainder Codes

V.G., Amit Sahai, Madhu Sudan

ConferenceFOCS 2000: 159-168

#20

List decoding algorithms for certain concatenated codes

V.G., Madhu Sudan

ConferenceSTOC 2000: 181-190

#19

Combinatorial Feature Selection Problems

Moses Charikar, V.G., Ravi Kumar, Sridhar Rajagopalan, Amit Sahai

ConferenceFOCS 2000: 631-640

#18

On the Hardness of 4-Coloring a 3-Colorable Graph

V.G., Sanjeev Khanna

JournalSIAM J. Discret. Math. 18(1) 30-40 (2004)
ConferenceCCC 2000: 188-197

#17

Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses

V.G.

JournalAlgorithmica 38(3) 451-469 (2004)
ConferenceAPPROX 2000: 155-166

#16

Rapidly Mixing Markov Chains: A Comparison of Techniques

V.G.

ManuscriptarXiv:1603.01512

#15

Evidence for a flat, accelerating Universe and the Lambda-CDM Model

V.G.

Manuscriptunpublished, 2000

1999

#14

Improved Decoding of Reed-Solomon and Algebraic-Geometric codes

V.G., Madhu Sudan

JournalIEEE Trans. Inf. Theory 45(6) 1757-1767 (1999)
ConferenceFOCS 1998: 28-39

#13

Multiclass Learning, Boosting, and Error-correcting codes

V.G., Amit Sahai

ConferenceCOLT 1999: 145-155

#12

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

V.G., Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis

JournalJ. Comput. Syst. Sci. 67(3) 473-496 (2003)
ConferenceSTOC 1999: 19-28

#11

The 2-Catalog Segmentation Problem

Yevgeniy Dodis, V.G., Sanjeev Khanna

ConferenceSODA 1999

#10

Enumerative aspects of certain subclasses of perfect graphs

V.G.

JournalDiscret. Math. 205(1-3) 97-117 (1999)

#9

Maximum Cut on Line and Total Graphs

V.G.

JournalDiscret. Appl. Math. 92(2-3) 217-221 (1999)

1998

#8

A tight characterization of NP with 3 query PCPs

V.G., Daniel Lewin, Madhu Sudan, Luca Trevisan

ConferenceFOCS 1998: 8-17

#7

A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds

V.G., C. Pandu Rangan

JournalInf. Process. Lett. 68(5) 241-248 (1998)

#6

The Vertex-disjoint Triangles Problem

V.G., C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong

ConferenceWG 1998: 26-37

1997

#5

Restrictions of Minimum Spanner Problems

V.G., M. S. Madanlal, Johann A. Makowsky, C. Pandu Rangan, Uri Rotics

JournalInformation and Computation

#4

Probabilistic Routing on Wavelength-routed Multistage, Hypercube and Debruijn Networks

V.G., Gurusamy Mohan, Chebiyyam Siva Ram Murthy

ConferenceHiPC 1997

#3

Intractability Results for Certain Graph-theoretic Optimization and Approximation Problems

V.G.

ManuscriptSenior Thesis, IIT Madras, May 1997

1996

#2

Approximate Triclique Coloring for Register Allocation

V.G., C. Pandu Rangan

JournalInformation Processing Letters 60 (1996)

#1

Tree 3-spanners on Interval, Permutation and Regular Bipartite graphs

M. S. Madanlal, V.G., C. Pandu Rangan

JournalInformation Processing Letters

Books

List Decoding of Error-Correcting Codes

Algorithmic Results in List Decoding

2026

Improved analysis of list-decodability of random linear codes: It's all about counting constraintsAbstract

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking InstancesAbstract

Strong Inapproximability for a Promise Rank ProblemAbstract

Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length ContractionAbstract

Explicit Constant-Alphabet Subspace Design CodesAbstract

Classification of Non-redundancy of Boolean Predicates of Arity 4Abstract

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design CodesAbstract

Quantum hierarchical locally recoverable codesAbstract

Maximal Recoverability: A Nexus of Coding TheoryAbstract

Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon CodesAbstract

The Richness of CSP Non-redundancyAbstract

Tight bounds for sparsifying random CSPsAbstract

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality CaseAbstract

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPsAbstract

Scheduling Problems with Constrained RejectionsAbstract

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness ResultsAbstract

2025

Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data StorageAbstract

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and LatticesAbstract

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-ChecksAbstract

New constructions of pseudorandom codesAbstract

Density Frankl-Rodl on the SphereAbstract

New Spectral Algorithms for Refuting Smoothed k-SATAbstract

Redundancy is all you needAbstract

Asymptotically Good Quantum Codes with Transversal Non-Clifford GatesAbstract

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETHAbstract

Semirandom Planted Clique via 1-norm Isometry PropertyAbstract

PCP-free APX-Hardness of Nearest Codeword and Minimum DistanceAbstract

Tight bounds for stream decodable error-correcting codesAbstract

Quantum LDPC Codes of Almost Linear Distance via Iterated Homological ProductsAbstract

Exponential Time Approximation for Coloring 3-Colorable GraphsAbstract

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable DecodingAbstract

Quantum locally recoverable codesAbstract

2024

Outlier Robust Multivariate Polynomial RegressionAbstract

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow CyclesAbstract

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \boldsymbol sqrt n Dimension ThresholdAbstract

Decoding quasi-cyclic quantum LDPC codesAbstract

Capacity-Achieving Gray CodesAbstract

Baby PIH: Parameterized Inapproximability of Min CSPAbstract

Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding TheoreticallyAbstract

Isolate and then Identify: Rethinking Adaptive Group TestingAbstract

Parameterized Inapproximability Hypothesis under ETHAbstract

Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fieldsAbstract

AG Codes Have No List-Decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential AlphabetsAbstract

Improved rate-distance trade-offs for quantum codes with restricted connectivityAbstract

2023

Hardness of Learning Boolean Functions from Label ProportionsAbstract

Efficient Algorithms for Semirandom Planted CSPs at the Refutation ThresholdAbstract

A Deterministic Construction of a Large Distance Code From the Wozencraft EnsembleAbstract

SDPs and Robust Satisfiability of Promise CSPAbstract

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ell_ p NormsAbstract

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP RefutationAbstract

Binary Error-Correcting Codes With Minimal Noiseless FeedbackAbstract

How Many Matrices Should I Prepare to Polarize Channels Optimally Fast?Abstract

On Expanding the Toolkit of Locality-Based Coded Computation to the Coordinates of Inputs

Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit ScalarsAbstract

2022

Punctured Low-Bias Codes Behave Like Random Linear CodesAbstract

Range Avoidance for Low-Depth Circuits and Connections to PseudorandomnessAbstract

Accelerating Polarization via Alphabet ExtensionAbstract

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique NumberAbstract

Beyond Single-Deletion Correcting Codes: Substitutions and TranspositionsAbstract

l_p-spread and restricted isometry properties of sparse random matricesAbstract

Sparsity and l_p-restricted isometryAbstract

Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no harder than RandomAbstract

Approximate Hypergraph Vertex Cover and Generalized Tuza's ConjectureAbstract

Improved Maximally Recoverable LRCs Using Skew PolynomialsAbstract

Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric CodesAbstract

2021

The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2Abstract

Revisiting a Lower Bound on the Redundancy of Linear Batch CodesAbstract

Visible rank and codes with localityAbstract

CNF Satisfiability in a Subspace and Related ProblemsAbstract

AC-DC: Amplification Curve Diagnostics for Covid-19 Group TestingAbstract

Conditional Dichotomy of Boolean Ordered Promise CSPsAbstract

Improved analysis of list-decodability of random linear codes: It's all about counting constraints

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances

Strong Inapproximability for a Promise Rank Problem

Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction

Explicit Constant-Alphabet Subspace Design Codes

Classification of Non-redundancy of Boolean Predicates of Arity 4

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes

Quantum hierarchical locally recoverable codes

Maximal Recoverability: A Nexus of Coding Theory

Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes

The Richness of CSP Non-redundancy

Tight bounds for sparsifying random CSPs

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs

Scheduling Problems with Constrained Rejections

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data Storage

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks

New constructions of pseudorandom codes

Density Frankl-Rodl on the Sphere

New Spectral Algorithms for Refuting Smoothed k-SAT

Redundancy is all you need

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Semirandom Planted Clique via 1-norm Isometry Property

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

Tight bounds for stream decodable error-correcting codes

Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products

Exponential Time Approximation for Coloring 3-Colorable Graphs

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding

Quantum locally recoverable codes

Outlier Robust Multivariate Polynomial Regression

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \boldsymbol sqrt n Dimension Threshold

Decoding quasi-cyclic quantum LDPC codes

Capacity-Achieving Gray Codes

Baby PIH: Parameterized Inapproximability of Min CSP

Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically

Isolate and then Identify: Rethinking Adaptive Group Testing

Parameterized Inapproximability Hypothesis under ETH

Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields

AG Codes Have No List-Decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential Alphabets

Improved rate-distance trade-offs for quantum codes with restricted connectivity

Hardness of Learning Boolean Functions from Label Proportions

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

A Deterministic Construction of a Large Distance Code From the Wozencraft Ensemble

SDPs and Robust Satisfiability of Promise CSP

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ell_ p Norms

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

Binary Error-Correcting Codes With Minimal Noiseless Feedback

How Many Matrices Should I Prepare to Polarize Channels Optimally Fast?

Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars

Punctured Low-Bias Codes Behave Like Random Linear Codes

Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness

Accelerating Polarization via Alphabet Extension

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions

l_p-spread and restricted isometry properties of sparse random matrices

Sparsity and l_p-restricted isometry

Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no harder than Random

Approximate Hypergraph Vertex Cover and Generalized Tuza's Conjecture

Improved Maximally Recoverable LRCs Using Skew Polynomials

Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes

The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2

Revisiting a Lower Bound on the Redundancy of Linear Batch Codes

Visible rank and codes with locality

CNF Satisfiability in a Subspace and Related Problems

AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing

Conditional Dichotomy of Boolean Ordered Promise CSPs

Linear Shannon Capacity of Cayley Graphs

Linear Programming Bounds for Almost-Balanced Binary Codes

A Locality-Based Lens for Coded Computation

Strongly refuting all semi-random Boolean CSPs

Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound

Efficient Linear and Affine Codes for Correcting Insertions/Deletions

Pseudobinomiality of the sticky random walk

Threshold Rates for Properties of Random Codes

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems

Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity