Venkatesan Guruswami

Venkatesan Guruswami's AcademicInfluence.com Rankings

Computer Science

#1845

World Rank

#1916

Historical Rank

Database

#3702

World Rank

#3854

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Venkatesan Guruswami Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Venkatesan Guruswami is a senior scientist at the Simons Institute for the Theory of Computing and Professor of EECS and Mathematics at the University of California, Berkeley. He did his high schooling at Padma Seshadri Bala Bhavan in Chennai, India. He completed his undergraduate in Computer Science from IIT Madras and his doctorate from Massachusetts Institute of Technology under the supervision of Madhu Sudan in 2001. After receiving his PhD, he spent a year at UC Berkeley as a Miller Fellow, and then was a member of the faculty at the University of Washington from 2002 to 2009. His primary area of research is computer science, and in particular on error-correcting codes. During 2007–2008, he visited the Institute for Advanced Study as a Member of School of Mathematics. He also visited SCS at Carnegie Mellon University during 2008–09 as a visiting faculty. From July 2009 through December 2020 he was a faculty member in the Computer Science Department in the School of Computer Science at Carnegie Mellon University.

(See a Problem?)

Venkatesan Guruswami's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Improved decoding of Reed-Solomon and algebraic-geometric codes (1998) (1213)
Clustering with qualitative information (2003) (439)
On profit-maximizing envy-free pricing (2005) (333)
CopyCatch: stopping group attacks by spotting lockstep behavior in social networks (2013) (310)
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems (1999) (255)
List decoding of error correcting codes (2001) (233)
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy (2005) (196)
Multiclass learning, boosting, and error-correcting codes (1999) (190)
A new multilayered PCP and the hardness of hypergraph vertex cover (2003) (187)
Correlation clustering with a fixed number of clusters (2005) (175)
Hardness of Learning Halfspaces with Noise (2006) (159)
Agnostic Learning of Monomials by Halfspaces Is Hard (2009) (148)
Repairing Reed-Solomon Codes (2015) (134)
Efficient Low-Redundancy Codes for Correcting Multiple Deletions (2015) (132)
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes (2007) (131)
Non-malleable Coding Against Bit-Wise and Split-State Tampering (2013) (121)
Linear-time encodable/decodable codes with near-optimal rate (2005) (119)
Optimal column-based low-rank matrix reconstruction (2011) (118)
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes (2012) (116)
Expander-based constructions of efficiently decodable codes (2001) (115)
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph (2008) (108)
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives (2011) (107)
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph (2011) (107)
List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition) (2005) (106)
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity (2013) (103)
Combinatorial bounds for list decoding (2002) (99)
Algorithmic Results in List Decoding (2006) (96)
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound (2013) (94)
List decoding algorithms for certain concatenated codes (2000) (91)
Capacity of Non-Malleable Codes (2013) (87)
Deletion Codes in the High-Noise and High-Rate Regimes (2014) (86)
On the hardness of 4-coloring a 3-collorable graph (2000) (86)
Algorithmic aspects of clique-transversal and clique-independent sets (2000) (86)
Explicit capacity-achieving list-decodable codes (2005) (83)
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets (2002) (80)
MaxMin allocation via degree lower-bounded arborescences (2009) (77)
Hardness of approximate hypergraph coloring (2000) (76)
A tight characterization of NP with 3 query PCPs (1998) (75)
Query Strategies for Priced Information (2002) (75)
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant (2011) (74)
How Long Can Optimal Locally Repairable Codes Be? (2018) (72)
Superlinear Lower Bounds for Multipass Graph Processing (2012) (72)
"Soft-decision" decoding of Chinese remainder codes (2000) (70)
Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes (2013) (69)
List decoding from erasures: bounds and code constructions (2001) (69)
Linear-Algebraic List Decoding of Folded Reed-Solomon Codes (2011) (65)
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs (2010) (61)
The complexity of the covering radius problem (2005) (60)
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate (2010) (60)
On the List-Decodability of Random Linear Codes (2010) (55)
Limits to List Decoding Reed-Solomon Codes (2006) (54)
Linear time encodable and list decodable codes (2003) (52)
Almost Euclidean subspaces of e N 1 via expander codes (2008) (50)
Explicit subspace designs (2013) (50)
Approximating np-hard problems efficient algorithms and their limits (2009) (49)
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard (2004) (47)
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy (2018) (47)
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth (2017) (47)
An Improved Bound on the Fraction of Correctable Deletions (2015) (47)
A Lower Bound on List Size for List Decoding (2005) (45)
(2+ε)-Sat Is NP-hard (2014) (43)
Hardness of routing with congestion in directed graphs (2007) (43)
Extensions to the Johnson bound (2001) (42)
Folded codes from function field towers and improved optimal rate list decoding (2012) (42)
Every Permutation CSP of arity 3 is Approximation Resistant (2009) (41)
New Hardness Results for Graph and Hypergraph Colorings (2016) (41)
List decoding tensor products and interleaved codes (2008) (41)
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses (2004) (40)
Optimal Rate Code Constructions for Computationally Simple Channels (2010) (38)
Tolerant Locally Testable Codes (2005) (38)
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes (2016) (37)
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey) (2016) (37)
Combinatorial feature selection problems (2000) (37)
List decoding with side information (2003) (34)
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals (2008) (34)
List decoding and property testing of error-correcting codes (2007) (34)
Embeddings and non-approximability of geometric problems (2003) (33)
Almost Euclidean subspaces of ℓ1N VIA expander codes (2007) (33)
Optimally Resilient Codes for List-Decoding From Insertions and Deletions (2019) (33)
Maximum Cut on Line and Total Graphs (1999) (33)
Linear-Time List Decoding in Error-Free Settings: (Extended Abstract) (2004) (33)
Communication With Imperfectly Shared Randomness (2014) (32)
Locally Testable Codes Require Redundant Testers (2009) (32)
Bypassing UGC from Some Optimal Geometric Inapproximability Results (2016) (32)
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) (2002) (31)
Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities (2017) (31)
Guessing secrets efficiently via list decoding (2002) (30)
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives (2011) (30)
Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs (2016) (30)
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness (2008) (30)
Concatenated codes can achieve list-decoding capacity (2008) (29)
2006 IEEE International Symposium on Information Theory (2006) (29)
The complexity of the covering radius problem on lattices and codes (2004) (29)
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs (2018) (28)
On representations of algebraic-geometry codes (2001) (27)
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere (2016) (27)
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs (2015) (27)
PCPs via the low-degree long code and hardness for constrained hypergraph coloring (2013) (27)
Optimal Rate List Decoding via Derivative Codes (2011) (27)
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets (2006) (26)
General strong polarization (2018) (26)
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes (2013) (26)
Iterative Decoding of Low-Density Parity Check Codes (2006) (26)
List decoding subspace codes from insertions and deletions (2012) (26)
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set (2011) (25)
Locality via Partially Lifted Codes (2017) (25)
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound (2020) (25)
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy (2017) (24)
An exponential lower bound on the sub-packetization of MSR codes (2019) (24)
Faster SDP Hierarchy Solvers for Local Rounding Algorithms (2012) (24)
Better extractors for better codes? (2004) (24)
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph (2017) (23)
Hardness of Max 3SAT with no mixed clauses (2005) (22)
Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes (2008) (22)
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields (2018) (22)
Coding Against Deletions in Oblivious and Online Models (2016) (22)
Constructions of codes from number fields (2001) (22)
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates (2004) (21)
Better Binary List Decodable Codes Via Multilevel Concatenation (2007) (21)
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets (2014) (20)
Is constraint satisfaction over two variables always easy? (2002) (20)
Query strategies for priced information (extended abstract) (2000) (20)
Efficient Linear and Affine Codes for Correcting Insertions/Deletions (2020) (20)
Approximating Non-Uniform Sparsest Cut Via Generalized Spectra (2011) (19)
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs (2010) (19)
Limits to list decodability of linear codes (2002) (19)
Robust Fourier and Polynomial Curve Fitting (2016) (18)
The Vertex-Disjoint Triangles Problem (1998) (18)
Decoding concatenated codes using soft information (2002) (17)
Explicit rank-metric codes list-decodable with optimal redundancy (2013) (17)
Beating Fredman-Komlós for perfect k-hashing (2019) (17)
Polynomial Time Decodable Codes for the Binary Deletion Channel (2017) (17)
Streaming Hardness of Unique Games (2018) (17)
Inapproximability of H-Transversal/Packing (2015) (17)
Inapproximability of Feedback Vertex Set for Bounded Length Cycles (2014) (17)
List Decoding of Binary Codes-A Brief Survey of Some Recent Results (2009) (16)
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (2014) (16)
Combinatorial Limitations of Average-Radius List-Decoding (2012) (16)
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs (2019) (16)
The Complexity of Making Unique Choices: Approximating 1-in- k SAT (2005) (16)
$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors (2019) (15)
Improved Inapproximability Results for Maximum k-Colorable Subgraph (2009) (15)
Cyclotomic function fields, Artin–Frobenius automorphisms, and list error correction with optimal rate (2010) (15)
The Quest for Strong Inapproximability Results with Perfect Completeness (2021) (15)
Finding Almost-Perfect Graph Bisections (2011) (15)
Guest column: error-correcting codes and expander graphs (2004) (14)
Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity (2022) (14)
Dimension Expanders via Rank Condensers (2014) (14)
Tight Bounds for Communication-Assisted Agreement Distillation (2016) (14)
Improved Maximally Recoverable LRCs Using Skew Polynomials (2020) (14)
The 2-catalog segmentation problem (1999) (14)
Error correction up to the information-theoretic limit (2009) (14)
On Maximally Recoverable Local Reconstruction Codes (2017) (13)
A 3-query PCP over integers (2007) (13)
Bounds for List-Decoding and List-Recovery of Random Linear Codes (2020) (13)
An improved bound on the zero-error list-decoding capacity of the 4/3 channel (2017) (13)
Explicit optimal-length locally repairable codes of distance 5 (2018) (13)
Polar Codes with Exponentially Small Error at Finite Block Length (2018) (13)
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number (2011) (13)
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs (2019) (12)
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere (2016) (12)
Hardness Amplification within NP against Deterministic Algorithms (2008) (12)
Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy (2016) (12)
On 2-Query Codeword Testing with Near-Perfect Completeness (2006) (11)
Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes (2014) (11)
Subspace Designs based on Algebraic Function Fields (2017) (11)
Inapproximability of Matrix p→q Norms (2018) (11)
Conditional Dichotomy of Boolean Ordered Promise CSPs (2021) (11)
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems (2020) (11)
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs (2015) (11)
Complexity of Approximating CSP with Balance / Hard Constraints (2014) (10)
Hardness of Low Congestion Routing in Directed Graphs (2006) (10)
∊-MSR codes with small sub-packetization (2017) (10)
The zero-rate threshold for adversarial bit-deletions is less than 1/2 (2021) (10)
Algebraic-geometric generalizations of the Parvaresh-Vardy codes (2005) (10)
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere (2016) (10)
Bridging Shannon and Hamming: List Error-Correction with Optimal Rate (2011) (10)
AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing (2020) (10)
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301) (2015) (10)
Algorithms for Modular Counting of Roots of Multivariate Polynomials (2006) (9)
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness (2019) (9)
The Existence of Concatenated Codes List-Decodable up to the Hamming Bound (2010) (9)
Lossless dimension expanders via linearized polynomials and subspace designs (2018) (9)
Extractors and condensers from univariate polynomials (2006) (9)
Almost Euclidean subspaces of $\ell_1^N$ via expander codes. (2007) (9)
(2 + epsilon)-Sat Is NP-Hard (2014) (9)
List Decoding in Average-Case Complexity and Pseudorandomness (2006) (9)
Non-Malleable Secret Sharing against Affine Tampering (2019) (9)
Enumerative aspects of certain subclasses of perfect graphs (1999) (9)
Optimal rate algebraic list decoding using narrow ray class fields (2013) (9)
The Kr-Packing Problem (2001) (9)
Hitting Sets for Low-Degree Polynomials with Optimal Density (2014) (9)
Explicit Capacity-achieving Codes for Worst-Case Additive Errors (2009) (8)
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises (2015) (8)
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models (2020) (8)
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions (2021) (8)
Reections on \Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes" (2002) (8)
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes (2008) (8)
∊-MSR Codes: Contacting Fewer Code Blocks for Exact Repair (2018) (8)
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems (2012) (7)
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers (2009) (7)
SDP Gaps for 2-to-1 and Other Label-Cover Variants (2010) (7)
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes (2017) (7)
Secret Sharing with Binary Shares (2018) (7)
Simple Proof of Hardness of Feedback Vertex Set (2016) (7)
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random (2021) (7)
A locality-based approach for coded computation (2020) (7)
Hardness Amplification via Space-Efficient Direct Products (2006) (7)
Explicit capacity-achieving list-decodable codes or decoding up to the singleton bound using folded Reed-Solomon codes (2006) (6)
Achieving list decoding capacity using folded Reed-Solomon codes (2006) (6)
Rainbow coloring hardness via low sensitivity polymorphisms (2020) (6)
On the List-Decodability of Random Linear Rank-Metric Codes (2017) (6)
Approximating Operator Norms via Generalized Krivine Rounding (2018) (6)
Sharp threshold rates for random codes (2020) (6)
8 List Decoding of Concatenated Codes (2004) (6)
Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs (2013) (5)
Towards a Characterization of Approximation Resistance for Symmetric CSPs (2017) (5)
Bridging between 0/1 and linear programming via random walks (2019) (5)
Limits to List Decoding Reed–Solomon Codes (2005) (5)
I T ] 5 O ct 2 00 6 Iterative Decoding of Low-Density Parity Check Codes ∗ ( An Introductory Survey ) (2008) (5)
Query-efficient checking of proofs and improved PCP characterizations of NP (1999) (5)
Leakage-Resilient Non-Malleable Secret Sharing in Non-compartmentalized Models (2019) (5)
New MDS codes with small sub-packetization and near-optimal repair bandwidth (2016) (5)
Unconditional proof of tightness of Johnson bound (2003) (5)
Hardness of Rainbow Coloring Hypergraphs (2017) (5)
The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses (1999) (5)
Approximating Bounded Occurrence Ordering CSPs (2012) (5)
Pseudobinomiality of the Sticky Random Walk (2020) (5)
On Representations of Algebraic-Geometric Codes (1998) (5)
Punctured Low-Bias Codes Behave Like Random Linear Codes (2021) (4)
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization (2019) (4)
CSPs with global modular constraints: algorithms and hardness via polynomial representations (2019) (4)
On Representations of Algebraic-Geometric Codes for List Decoding (2000) (4)
Strongly refuting all semi-random Boolean CSPs (2020) (4)
Linear-time Codes to Correct a Maximum Possible Fraction of Errors (2001) (4)
New Approximation Algorithms for Degree Lower-bounded Arborescences and Max-Min Allocation (2009) (4)
Combinatorial limitations of a strong form of list decoding (2012) (4)
An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes (2021) (3)
Efficiently List-Decodable Punctured Reed-Muller Codes (2015) (3)
Efficiently Decodable Codes for the Binary Deletion Channel (2017) (3)
The K_r-packing problem (2001) (3)
Threshold Rates for Properties of Random Codes (2022) (3)
An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel (2020) (3)
Ip-spread and restricted isometry properties of sparse random matrices (2021) (3)
Efficient list decoding of punctured Reed-Muller codes (2015) (3)
Algorithmic Polarization for Hidden Markov Models (2018) (3)
Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction (2008) (3)
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation (2022) (2)
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs (2017) (2)
Accelerating Polarization via Alphabet Extension (2022) (2)
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime (2015) (2)
Parameterized Inapproximability of Exact Cover and Nearest Codeword (2019) (2)
Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra (2011) (2)
Inapproximability results for set splitting and satisfiability problems with no mixed clauses (2000) (2)
Complexity of Approximating CSP with Balance / Hard Constraints (2015) (2)
Inapproximability of Matrix $p\rightarrow q$ Norms (2018) (2)
Soft Decoding, Dual BCH Codes, and Better List-Decodable $\varepsilon$-Biased Codes (2011) (2)
A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds (1998) (2)
Codes correcting deletions in oblivious and random models (2016) (2)
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity (2021) (2)
SDPs and Robust Satisfiability of Promise CSP (2022) (1)
Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008) (2011) (1)
Explicit subspace designs (2014) (1)
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all 𝓁p Norms (2022) (1)
List Decoding and Pseudorandom Constructions (2007) (1)
1 Asymptotically good codes and Gilbert-Varshamov bound (2010) (1)
Expander codes over reals, Euclidean sections, and compressed sensing (2009) (1)
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness (2022) (1)
Improved Column-Based Low-Rank Matrix Reconstruction (2011) (1)
PCPs via the low-degree long code and hardness for constrained hypergraph coloring (2015) (1)
Nearly Optimal NP-Hardness of Unique Coverage (2016) (1)
Non-malleable Coding Against Bit-Wise and Split-State Tampering (2015) (1)
An Algorithmic Study of the Hypergraph Turán Problem (2020) (1)
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture (2020) (1)
Better Binary List Decodable Codes Via Multilevel (2009) (1)
Visible Rank and Codes with Locality (2021) (1)
6 Reed-Solomon and Algebraic-Geometric Codes (2004) (1)
10 List Decoding from Erasures (2004) (0)
3 Johnson-Type Bounds and Applications to List Decoding (2004) (0)
2 Preliminaries and Monograph Structure (2004) (0)
DECODING TENSOR PRODUCTS AND INTERLEAVED CODES (2008) (0)
11 Linear-Time Codes for Unique Decoding (2004) (0)
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number (2022) (0)
Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk) (2013) (0)
15-251 : Great Theoretical Ideas In Computer Science Notes on Linear Algebra (2011) (0)
Lecture 10 : Justesen Codes and Reed-Solomon Decoding 1 November 2006 (2006) (0)
CSE 533 : Error-Correcting Codes ( Autumn 2006 ) Lecture 4 : Proof of Shannon ’ s theorem and an explicit code October (2006) (0)
The query complexity of estimating weighted averages (2011) (0)
Session details: Session 10B (2011) (0)
9 New, Expander-Based List Decodable Codes (2004) (0)
List De oding from Erasures : Bounds and Code Constru tionsVenkatesan Guruswami ? (2001) (0)
Guessing secrets efficiently via list decoding (extended abstract) (2002) (0)
13 Concluding Remarks (2004) (0)
Revisiting Alphabet Reduction in Dinur's PCP (2019) (0)
Session details: Session 8B (2011) (0)
I T ] 8 F eb 2 01 8 General Strong Polarization (2018) (0)
Binary Error-Correcting Codes with Minimal Noiseless Feedback (2022) (0)
Guest Editors' foreword (2004) (0)
C C ] 1 2 N ov 2 01 8 Streaming Hardness of Unique Games (2018) (0)
Sparsity and $\ell_p$-Restricted Isometry (2022) (0)
Spectral Graph Theory Lecture 11 Introduction to Coding Theory (2009) (0)
Hardness Amplication via Space-Ecien t Direct Products (2005) (0)
Cse 521 Winter 2006 Notes on Hashing (0)
Foreword This chapter is based on lecture notes from coding theory courses taught by Venkatesan (2018) (0)
Combining LPs and Ring Equations via Structured Polymorphisms (2018) (0)
Special Issue “Conference on Computational Complexity 2006” Guest Editors’ Foreword (2007) (0)
A GMD Decoding of Concatenated Codes (2004) (0)
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields (2023) (0)
The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2 (2023) (0)
Lecture 7: Composition and Linearity Testing (2005) (0)
Session details: 1A (2008) (0)
7 A Unified Framework for List Decoding of Algebraic Codes (2004) (0)
List Error-Correction with Optimal Information Rate (Invited Talk) (2008) (0)
Fundamental Limit of Error-Correction Achieved (2008) (0)
Session details: 7A (2008) (0)
CSE 533 : The PCP Theorem and Hardness of Approximation ( Autumn 2005 ) Lecture 14 : Label Cover Hardness : Application to Set Cover (2005) (0)
𝓁p-Spread Properties of Sparse Matrices (2021) (0)
Sparsity and 𝓁p-Restricted Isometry (2022) (0)
ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair (2020) (0)
CSE 533 : Error-Correcting Codes ( Autumn 2006 ) Lecture 8 : Reed Muller Codes (2006) (0)
4 Limits to List Decodability (2004) (0)
Deterministic Hardness Amplification via Local GMD Decoding (2007) (0)
General Strong Polarization (2018) (0)
12 Sample Applications Outside Coding Theory (2004) (0)
A locality-based lens for coded computation (2021) (0)
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover (2017) (0)
Linear Shannon Capacity of Cayley Graphs (2020) (0)
5 List Decodability Vs. Rate (2004) (0)
Decoding Reed-Solomon Codes (2008) (0)
( 2 + ε )-S AT is NP-hard ∗ (2014) (0)
Lecture 15: Set Cover Hardness and Testing Long Codes We Will First Recall the Reduction from Label Cover to Set Cover That Was Covered in the Last Lecture. We Start with a Label Cover Instance (2005) (0)
The polymorphic gateway between structure and algorithms: Beyond CSPs (2018) (0)
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations (2022) (0)
Revisiting a Lower Bound on the Redundancy of Linear Batch Codes (2021) (0)
Algebra & Number Theory (2010) (0)
CNF Satisfiability in a Subspace and Related Problems (2021) (0)
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble (2023) (0)
Linear Programming Bounds for Almost-Balanced Binary Codes (2021) (0)
2 0 Ju n 20 11 Optimal rate list decoding via derivative codes (2015) (0)
Explicit Capacity-Achieving List-Decodable Codes or Decoding Folded Reed-Solomon Codes up to their Distance (2005) (0)
Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs (2021) (0)
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms (2023) (0)
C C ] 2 7 Ju l 2 01 7 Communication with Imperfectly Shared Randomness ∗ (2018) (0)

This paper list is powered by the following services:

Other Resources About Venkatesan Guruswami

What Schools Are Affiliated With Venkatesan Guruswami?

Venkatesan Guruswami is affiliated with the following schools: