pith. sign in

Venkatesan Guruswami

Identifiers

  • name variant Venkatesan Guruswami 0.60 · backfill

Papers (74)

  1. Quantum Hierarchical Locally Recoverable Codes cs.IT · 2026 · author #1
  2. Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances cs.DM · 2026 · author #2
  3. Strong Inapproximability for a Promise Rank Problem cs.CC · 2026 · author #1
  4. Multiplicative error set system sparsification: A simpler proof via chain length contraction math.CO · 2026 · author #2
  5. Explicit Constant-Alphabet Subspace Design Codes cs.IT · 2026 · author #2
  6. Density Frankl-R\"{o}dl on the Sphere math.PR · 2025 · author #1
  7. Redundancy Is All You Need (for CSP Sparsification) cs.DS · 2024 · author #2
  8. Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization cs.DS · 2019 · author #1
  9. Parameterized Inapproximability of Exact Cover and Nearest Codeword cs.CC · 2019 · author #1
  10. Bridging between 0/1 and Linear Programming via Random Walks cs.DS · 2019 · author #2
  11. Leakage-Resilient Non-Malleable Secret Sharing in Non-compartmentalized Models cs.CR · 2019 · author #3
  12. CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations cs.CC · 2019 · author #3
  13. Algorithmic Polarization for Hidden Markov Models cs.IT · 2018 · author #1
  14. Constructions of maximally recoverable local reconstruction codes via function fields cs.IT · 2018 · author #1
  15. Secret Sharing with Binary Shares cs.CR · 2018 · author #3
  16. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs cs.CC · 2018 · author #2
  17. $\epsilon$-MSR Codes: Contacting Fewer Code Blocks for Exact Repair cs.IT · 2018 · author #1
  18. How long can optimal locally repairable codes be? cs.IT · 2018 · author #1
  19. Beating Fredman-Koml\'{o}s for perfect $k$-hashing cs.IT · 2018 · author #1
  20. Inapproximability of Matrix $p\rightarrow q$ Norms cs.CC · 2018 · author #3
  21. On the List-Decodability of Random Linear Rank-Metric Codes cs.CC · 2017 · author #1
  22. Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities cs.IT · 2017 · author #2
  23. MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth cs.IT · 2017 · author #3
  24. Polynomial time decodable codes for the binary deletion channel cs.IT · 2017 · author #1
  25. Locality via Partially Lifted Codes cs.IT · 2017 · author #2
  26. Subspace Designs based on Algebraic Function Fields cs.CC · 2017 · author #1
  27. Coding against deletions in oblivious and online models cs.IT · 2016 · author #1
  28. Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere cs.DS · 2016 · author #3
  29. New MDS codes with small sub-packetization and near-optimal repair bandwidth cs.IT · 2016 · author #1
  30. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes cs.IT · 2016 · author #1
  31. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere cs.CC · 2016 · author #2
  32. Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey) cs.DS · 2016 · author #1
  33. Repairing Reed-Solomon Codes cs.IT · 2015 · author #1
  34. Efficiently list-decodable punctured Reed-Muller codes cs.IT · 2015 · author #1
  35. Efficient Low-Redundancy Codes for Correcting Multiple Deletions cs.IT · 2015 · author #2
  36. An improved bound on the fraction of correctable deletions cs.IT · 2015 · author #2
  37. Approximate Hypergraph Coloring under Low-discrepancy and Related Promises cs.DS · 2015 · author #2
  38. Inapproximability of $H$-Transversal/Packing cs.CC · 2015 · author #1
  39. Dimension Expanders via Rank Condensers cs.CC · 2014 · author #2
  40. An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets cs.IT · 2014 · author #1
  41. Deletion codes in the high-noise and high-rate regimes cs.IT · 2014 · author #1
  42. Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs cs.DS · 2013 · author #1
  43. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes cs.CC · 2013 · author #1
  44. Explicit rank-metric codes list-decodable with optimal redundancy cs.IT · 2013 · author #1
  45. Non-Malleable Coding Against Bit-wise and Split-State Tampering cs.IT · 2013 · author #2
  46. Capacity of Non-Malleable Codes cs.IT · 2013 · author #2
  47. Polar Codes: Speed of polarization and polynomial gap to capacity cs.IT · 2013 · author #1
  48. Optimal rate algebraic list decoding using narrow ray class fields math.NT · 2013 · author #1
  49. Superlinear lower bounds for multipass graph processing cs.CC · 2012 · author #1
  50. Faster SDP hierarchy solvers for local rounding algorithms cs.DS · 2012 · author #1
  51. Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes cs.IT · 2012 · author #2
  52. Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding cs.IT · 2012 · author #1
  53. Combinatorial limitations of average-radius list-decoding cs.IT · 2012 · author #1
  54. Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems cs.CC · 2012 · author #1
  55. List decoding subspace codes from insertions and deletions cs.IT · 2012 · author #1
  56. Approximating Non-Uniform Sparsest Cut via Generalized Spectra cs.DS · 2011 · author #1
  57. Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph cs.DS · 2011 · author #3
  58. Optimal rate list decoding via derivative codes cs.IT · 2011 · author #1
  59. Linear-algebraic list decoding of folded Reed-Solomon codes cs.IT · 2011 · author #1
  60. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives cs.CC · 2011 · author #1
  61. Optimal Column-Based Low-Rank Matrix Reconstruction cs.DS · 2011 · author #1
  62. Agnostic Learning of Monomials by Halfspaces is Hard cs.CC · 2010 · author #2
  63. Optimal-Rate Code Constructions for Computationally Simple Channels cs.IT · 2010 · author #1
  64. On the List-Decodability of Random Linear Codes cs.IT · 2010 · author #1
  65. Explicit Capacity-achieving Codes for Worst-Case Additive Errors cs.IT · 2009 · author #1
  66. Improved Inapproximability Results for Maximum k-Colorable Subgraph cs.CC · 2009 · author #1
  67. List Decoding Tensor Products and Interleaved Codes cs.IT · 2008 · author #2
  68. Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes math.NT · 2008 · author #1
  69. Almost Euclidean subspaces of \ell_1^N via expander codes math.MG · 2007 · author #1
  70. Iterative Decoding of Low-Density Parity Check Codes (A Survey) cs.IT · 2006 · author #1
  71. Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy cs.IT · 2005 · author #1
  72. Correlation Clustering with a Fixed Number of Clusters cs.DS · 2005 · author #2
  73. Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard cs.CC · 2004 · author #1
  74. A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover cs.CC · 2003 · author #2

Mentions

  • 2606.06736 #1 · arxiv_oai · confidence 0.70 Venkatesan Guruswami
  • 1509.04764 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1508.00603 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1507.06175 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1507.01719 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1506.06444 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1506.06302 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1411.7455 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1411.6993 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1411.6667 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1312.3024 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1311.7407 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1311.7084 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1309.1151 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1309.0458 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1304.4321 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1302.6660 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1212.6925 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1207.4372 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1207.1140 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1204.4209 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1202.6086 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1202.6071 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1202.0535 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1112.4109 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1110.1360 #3 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1106.3951 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1106.0436 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1104.4746 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1104.1732 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 2605.19055 #2 · arxiv_oai · confidence 0.70 Venkatesan Guruswami
  • 2411.03451 #2 · arxiv_oai · confidence 0.70 Venkatesan Guruswami
  • 1012.0729 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1004.4017 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 1001.1386 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 0912.0965 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 0910.2271 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 0811.4395 #2 · backfill · confidence 0.70 Venkatesan Guruswami
  • 0811.4139 #1 · backfill · confidence 0.70 Venkatesan Guruswami
  • 0709.0887 #1 · backfill · confidence 0.70 Venkatesan Guruswami

Frequent Coauthors