vix.ing · top · new · best · stats · spec

Guruswami, Venkatesan

  1. Repairing Reed-Solomon Codes
    2015/09/15 by Venkatesan Guruswami, Mary Wootters, Guruswami, Venkatesan +1 · 1 voice · 4 citations
    #cs.IT #cs.CC
  2. Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
    2005/11/18 by Guruswami, Venkatesan, Rudra, Atri · 7 citations
    #FOS: Computer and information sciences #H.1.1 #Information Theory (cs.IT)
  3. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
    2017/04/06 by Brakensiek, Joshua, Guruswami, Venkatesan · 5 citations
    #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
  4. Agnostic Learning of Monomials by Halfspaces is Hard
    2010/12/03 by Feldman, Vitaly, Guruswami, Venkatesan, Raghavendra, Prasad +1 · 4 citations
    #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  5. A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
    2003/04/19 by Irit Dinur, Venkatesan Guruswami, Dinur, Irit +5 · 3 citations
    Computer Science · #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #cs.CC
  6. How long can optimal locally repairable codes be?
    2018/07/03 by Guruswami, Venkatesan, Xing, Chaoping, Yuan, Chen · 4 citations
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  7. A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
    2023/08/29 by Omar Alrabiah, Venkatesan Guruswami, Alrabiah, Omar +5 · 7 citations
    Computer Science · #Advanced Data Storage Technologies #Cellular Automata and Applications #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  8. Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
    2021/09/09 by Guruswami, Venkatesan, Kothari, Pravesh K., Manohar, Peter · 5 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  9. Quantum Locally Recoverable Codes
    2023/11/15 by Louis Golowich, Golowich, Louis, Venkatesan Guruswami +1 · 7 citations
    Computer Science · #Quantum Computing Algorithms and Architecture #Advanced Data Storage Technologies #Cloud Computing and Resource Management
  10. Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
    2016/03/04 by Guruswami, Venkatesan · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  11. Optimal rate list decoding over bounded alphabets using algebraic-geometric codes
    2017/08/03 by Venkatesan Guruswami, Guruswami, Venkatesan, Chaoping Xing +1 · 3 citations
    Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT) #graph theory and CDMA systems
  12. Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
    2004/05/04 by Guruswami, Venkatesan, Vardy, Alexander · 2 citations
    #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #E.4 #F.1.3 #F.2.1 #FOS: Computer and information sciences #Information Theory (cs.IT)
  13. Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
    2024/08/17 by Golowich, Louis, Guruswami, Venkatesan · 8 citations
    #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)
  14. On the List-Decodability of Random Linear Codes
    2010/01/09 by Guruswami, Venkatesan, Hastad, Johan, Kopparty, Swastik · 2 citations
    #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  15. Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
    2011/10/06 by Bhaskara, Aditya, Charikar, Moses, Guruswami, Venkatesan +2 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
    2023/04/19 by Omar Alrabiah, Alrabiah, Omar, Guo, Zeyu +5 · 5 citations
    Computer Science · Social Sciences · #Coding theory and cryptography #Islamic Finance and Communication #Cooperative Communication and Network Coding
  17. Dimension Expanders via Rank Condensers
    2014/11/27 by Forbes, Michael A., Guruswami, Venkatesan · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  18. Strongly refuting all semi-random Boolean CSPs
    2020/09/17 by Jackson Abascal, Venkatesan Guruswami, Abascal, Jackson +3 · 3 citations
    Computer Science · #Constraint Satisfaction and Optimization #Complexity and Algorithms in Graphs #Formal Methods in Verification
  19. MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth
    2017/09/24 by Rawat, Ankit Singh, Tamo, Itzhak, Guruswami, Venkatesan +1 · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  20. Beating Fredman-Komlós for perfect k-hashing
    2018/05/10 by Guruswami, Venkatesan, Riazanov, Andrii · 2 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  21. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
    2018/07/13 by Brakensiek, Joshua, Guruswami, Venkatesan · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Optimization and Control (math.OC)
  22. Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities
    2017/10/27 by Sivakanth Gopi, Gopi, Sivakanth, Venkatesan Guruswami +3 · 2 citations
    Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Cellular Automata and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  23. Correlation Clustering with a Fixed Number of Clusters
    2005/04/06 by Ioannis Giotis, Giotis, Ioannis, Venkatesan Guruswami +1 · 1 citation
    Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Voting Systems #Multi-Criteria Decision Making #Rough Sets and Fuzzy Logic #cs.DS
  24. Improved Maximally Recoverable LRCs using Skew Polynomials
    2020/12/14 by Sivakanth Gopi, Gopi, Sivakanth, Venkatesan Guruswami +1 · 2 citations
    Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Computational Complexity (cs.CC) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Rings and Algebras (math.RA)
  25. Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
    2008/11/25 by Guruswami, Venkatesan · 1 citation
    #11R60 (primary) 11G30 #14Q05 (secondary) #94B27 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT)
  26. List Decoding Tensor Products and Interleaved Codes
    2008/11/26 by Gopalan, Parikshit, Guruswami, Venkatesan, Raghavendra, Prasad · 1 citation
    #E.4 #F.2.2 #FOS: Computer and information sciences #Information Theory (cs.IT)
  27. Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
    2024/10/03 by Bhattiprolu, Vijay, Guruswami, Venkatesan, Lee, Euiwoong +1 · 4 citations
    #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
  28. Explicit two-deletion codes with redundancy matching the existential bound
    2020/07/21 by Guruswami, Venkatesan, Håstad, Johan · 2 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT)
  29. Binary Error-Correcting Codes with Minimal Noiseless Feedback
    2022/12/12 by Meghal Gupta, Venkatesan Guruswami, Gupta, Meghal +3 · 2 citations
    Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
  30. Folded Codes from Function Field Towers and Improved Optimal Rate List\n Decoding
    2012/04/18 by Venkatesan Guruswami, Guruswami, Venkatesan, Chaoping Xing +1 · 1 citation
    Computer Science · #Advanced Data Storage Technologies #Algebraic Geometry (math.AG) #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT)
  31. Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
    2012/07/04 by Cheraghchi, Mahdi, Guruswami, Venkatesan, Velingker, Ameya · 1 citation
    #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)
  32. Superlinear lower bounds for multipass graph processing
    2012/12/31 by Guruswami, Venkatesan, Onak, Krzysztof · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  33. Capacity of Non-Malleable Codes
    2013/09/02 by Mahdi Cheraghchi, Venkatesan Guruswami, Cheraghchi, Mahdi +1 · 1 citation
    Computer Science · Engineering · #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
  34. The zero-rate threshold for adversarial bit-deletions is less than 1/2
    2021/06/09 by Venkatesan Guruswami, Xiaoyu He, Guruswami, Venkatesan +3 · 2 citations
    Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  35. Subspace Designs based on Algebraic Function Fields
    2017/04/20 by Guruswami, Venkatesan, Xing, Chaoping, Yuan, Chen · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
  36. Inapproximability of Matrix p→ q Norms
    2018/02/21 by Vijay Bhattiprolu, Mrinalkanti Ghosh, Bhattiprolu, Vijay +7 · 1 citation
    Mathematics · Engineering · #Mathematical Approximation and Integration #Advanced Numerical Analysis Techniques #Advanced Optimization Algorithms Research
  37. Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
    2023/09/28 by Guruswami, Venkatesan, Hsieh, Jun-Ting, Kothari, Pravesh K. +1 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  38. Secret Sharing with Binary Shares
    2018/08/09 by Lin, Fuchun, Cheraghchi, Mahdi, Guruswami, Venkatesan +2 · 1 citation
    #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)
  39. On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
    2023/12/28 by Guruswami, Venkatesan, C. S. Karthik, Pasin Manurangsi +4 · 2 citations
    Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #semigroups and automata theory
  40. Outlier Robust Multivariate Polynomial Regression
    2024/03/14 by Arora, Vipul, Bhattacharyya, Arnab, Boban, Mathews +2 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  41. Efficient Linear and Affine Codes for Correcting Insertions/Deletions
    2020/07/17 by Cheng, Kuan, Guruswami, Venkatesan, Haeupler, Bernhard +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  42. New constructions of pseudorandom codes
    2024/09/11 by Ghentiyala, Surendra, Guruswami, Venkatesan · 2 citations
    #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
  43. Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
    2021/12/18 by Gabrys, Ryan, Guruswami, Venkatesan, Ribeiro, João +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  44. Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms
    2022/11/15 by Huck Bennett, Mahdi Cheraghchi, Bennett, Huck +5 · 1 citation
    Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems
  45. SDPs and Robust Satisfiability of Promise CSP
    2022/11/15 by Joshua Brakensiek, Brakensiek, Joshua, Venkatesan Guruswami +3 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
  46. AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
    2023/08/25 by Omar Alrabiah, Venkatesan Guruswami, Alrabiah, Omar +3 · 1 citation
    Computer Science · Engineering · #Coding theory and cryptography #Cooperative Communication and Network Coding #graph theory and CDMA systems
  47. Redundancy Is All You Need (for CSP Sparsification)
    2024/11/05 by Joshua Brakensiek, Brakensiek, Joshua, Venkatesan Guruswami +1 · 2 citations
    Health Professions · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Logic in Computer Science (cs.LO) #Quality and Safety in Healthcare
  48. Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
    2023/11/14 by Venkatesan Guruswami, Hsin-Po Wang, Guruswami, Venkatesan +1 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · Medicine · #Advanced biosensing and bioanalysis techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data #SARS-CoV-2 detection and testing
  49. Baby PIH: Parameterized Inapproximability of Min CSP
    2023/10/25 by Guruswami, Venkatesan, Ren, Xuandi, Sandeep, Sai · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  50. Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
    2024/04/08 by Alrabiah, Omar, Guruswami, Venkatesan · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
  51. Decoding Quasi-Cyclic Quantum LDPC Codes
    2024/11/07 by Golowich, Louis, Guruswami, Venkatesan · 1 citation
    #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)
  52. Quantum LDPC Codes of Almost Linear Distance via Homological Products
    2024/11/06 by Golowich, Louis, Guruswami, Venkatesan · 2 citations
    #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)
  53. PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
    2025/03/14 by Bhattiprolu, Vijay, Guruswami, Venkatesan, Ren, Xuandi · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences