Madhu Sudan

Publication Activity (10 Years)

Years Active: 2021-2024
Publications (10 Years): 39

Top Topics

Arc Consistency

Solving Constraint Satisfaction Problems

Top Venues

Electron. Colloquium Comput. Complex.

IEEE Trans. Inf. Theory

Publications

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
Local Correction of Linear Functions over the Boolean Cube. CoRR (2024)
Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
Errors are Robustly Tamed in Cumulative Knowledge Processes. COLT (2024)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of All Finite CSPs. J. ACM 71 (2) (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Code Sparsification and its Applications. SODA (2024)
Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. Comput. Complex. 33 (1) (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR (2024)
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
Local Correction of Linear Functions over the Boolean Cube. Electron. Colloquium Comput. Complex. (2024)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Decoding Multivariate Multiplicity Codes on Product Sets. IEEE Trans. Inf. Theory 70 (1) (2024)
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
Local Correction of Linear Functions over the Boolean Cube. STOC (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP (2024)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Ideal-Theoretic Explanation of Capacity-Achieving Decoding. IEEE Trans. Inf. Theory 70 (2) (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR (2024)
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
Code Sparsification and its Applications. CoRR (2023)
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan
Is This Correct? Let's Check! ITCS (2023)
Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
Combinative Cumulative Knowledge Processes. CoRR (2023)
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan
An Improved Line-Point Low-Degree Test. CoRR (2023)
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS (2023)
Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. CoRR (2023)
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan
An Improved Line-Point Low-Degree Test. Electron. Colloquium Comput. Complex. (2023)
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
Low-Degree Testing Over Grids. CoRR (2023)
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
Low-Degree Testing over Grids. APPROX/RANDOM (2023)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. SODA (2023)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. (2022)
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming beyond sketching for Maximum Directed Cut. Electron. Colloquium Comput. Complex. (2022)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming beyond sketching for Maximum Directed Cut. CoRR (2022)
Madhu Sudan
Streaming and Sketching Complexity of CSPs: A survey. CoRR (2022)
Noah Singer, Madhu Sudan
Point-hyperplane Incidence Geometry and the Log-rank Conjecture. ACM Trans. Comput. Theory 14 (2) (2022)
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
General Strong Polarization. J. ACM 69 (2) (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. CoRR (2022)
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan
Is this correct? Let's check! CoRR (2022)
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. Electron. Colloquium Comput. Complex. (2022)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance. IEEE Trans. Inf. Theory 68 (10) (2022)
Madhu Sudan
Streaming and Sketching Complexity of CSPs: A survey. Electron. Colloquium Comput. Complex. (2022)
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM (2022)
Madhu Sudan
Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). ICALP (2022)
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming complexity of CSPs with randomly ordered constraints. CoRR (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear space streaming lower bounds for approximating CSPs. STOC (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2021)