Venkatesan Guruswami
- Repairing Reed-Solomon Codes
2015/09/15 by Venkatesan Guruswami, Mary Wootters, Guruswami, Venkatesan +1 · 1 voice · 4 citations
#cs.IT #cs.CC
- 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
- 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)
- 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
- Quantum Locally Recoverable Codes
2023/11/15 by Louis Golowich, Venkatesan Guruswami, Golowich, Louis +1 · 6 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Advanced Data Storage Technologies #Cloud Computing and Resource Management
- 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
- 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)
- Strongly refuting all semi-random Boolean CSPs
2020/09/17 by Jackson Abascal, Venkatesan Guruswami, Abascal, Jackson +3 · 2 citations
Computer Science · #Constraint Satisfaction and Optimization #Complexity and Algorithms in Graphs #Formal Methods in Verification
- 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
- 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)
- 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
- Capacity of Non-Malleable Codes
2013/09/02 by Mahdi Cheraghchi, Cheraghchi, Mahdi, Venkatesan Guruswami +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
- 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)
- 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
- 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
- SDPs and Robust Satisfiability of Promise CSP
2022/11/15 by Joshua Brakensiek, Venkatesan Guruswami, Brakensiek, Joshua +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)
- AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
2023/08/25 by Omar Alrabiah, Alrabiah, Omar, Venkatesan Guruswami +3 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Cooperative Communication and Network Coding #graph theory and CDMA systems
- Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
2023/11/14 by Venkatesan Guruswami, Guruswami, Venkatesan, Hsin-Po Wang +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
- Redundancy Is All You Need (for CSP Sparsification)
2024/11/05 by Joshua Brakensiek, Brakensiek, Joshua, Venkatesan Guruswami +1 · 1 citation
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
- Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
2026/07/29 by Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
Computer Science · #cs.CC #cs.DS