Madhu Sudan

1. Approximate Graph Coloring by Semidefinite Programming
   1998/12/08 by David Karger, Rajeev Motwani, Madhu Sudan · 5 citations
   Computer Science · #cs.DS
2. Streaming Lower Bounds for Approximating MAX-CUT
   2014/09/07 by Michael Kapralov, Kapralov, Michael, Sanjeev Khanna +3 · 6 citations
   Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
3. Linear Space Streaming Lower Bounds for Approximating CSPs
   2021/06/24 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +7 · 6 citations
   Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
4. Code Sparsification and its Applications
   2023/11/01 by Sanjeev Khanna, Khanna, Sanjeev, Aaron Putterman +3 · 6 citations
   Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
5. Sketching approximability of all finite CSPs
   2021/05/03 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 5 citations
   Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Machine Learning and Algorithms #Scheduling and Optimization Algorithms
6. Optimal Testing of Reed-Muller Codes
   2009/10/04 by Arnab Bhattacharyya, Bhattacharyya, Arnab, Swastik Kopparty +7 · 2 citations
   Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning and Algorithms #semigroups and automata theory
7. Streaming and Sketching Complexity of CSPs: A survey
   2022/05/05 by Madhu Sudan, Sudan, Madhu · 3 citations
   Computer Science · #Constraint Satisfaction and Optimization #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
8. Synchronization Strings: List Decoding for Insertions and Deletions
   2018/02/23 by Bernhard Haeupler, Amirbehshad Shahrasbi, Haeupler, Bernhard +3 · 2 citations
   Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
9. Efficient Algorithms and New Characterizations for CSP Sparsification
   2024/04/09 by Sanjeev Khanna, Khanna, Sanjeev, Aaron Putterman +3 · 4 citations
   Computer Science · Engineering · #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
10. Kakeya-type sets in finite vector spaces
    2010/03/19 by Swastik Kopparty, Vsevolod F. Lev, Kopparty, Swastik +5 · 1 citation
    Computer Science · Mathematics · #05B25 #51E20 #52C17. #Advanced Topology and Set Theory #Coding theory and cryptography #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)
11. New affine-invariant codes from lifting
    2012/08/27 by Alan Guo, Swastik Kopparty, Guo, Alan +3 · 1 citation
    Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
12. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
    2024/07/04 by Sanjeev Khanna, Khanna, Sanjeev, Aaron Putterman +3 · 3 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Low-power high-performance VLSI design #Parallel Computing and Optimization Techniques #VLSI and FPGA Design Techniques
13. Streaming Algorithms via Local Algorithms for Maximum Directed Cut
    2024/11/28 by Raghuvansh R. Saxena, Saxena, Raghuvansh R., Noah Singer +5 · 6 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
14. Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
    2022/11/08 by Raghuvansh R. Saxena, Saxena, Raghuvansh R., Noah Singer +5 · 4 citations
    Computer Science · #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
15. Approximability of all Boolean CSPs with linear sketches
    2021/02/24 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #semigroups and automata theory
16. On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
    2023/08/29 by Kuan Cheng, Cheng, Kuan, Elena Grigorescu +7 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms #Molecular Biology Techniques and Applications
17. Local Correction of Linear Functions over the Boolean Cube
    2024/03/29 by Prashanth Amireddy, Amireddy, Prashanth, Amik Raj Behera +7 · 1 citation
    Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation
18. A Unified Theory of Sparsification
    2026/07/17 by Sanjeev Khanna, Aaron Putterman, Madhu Sudan
    #cs.DS