Madhu Sudan

Publication Activity (10 Years)

Years Active: 1990-2022
Publications (10 Years): 71

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

SODA

ITCS

Publications

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. FOCS (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming Approximation Resistance of Every Ordering CSP. APPROX-RANDOM (2021)
Noah Singer, Madhu Sudan
Point-hyperplane incidence geometry and the log-rank conjecture. CoRR (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. Electron. Colloquium Comput. Complex. 28 (2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Ideal-theoretic Explanation of Capacity-achieving Decoding. CoRR (2021)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. ISIT (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. CoRR (2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Decoding multivariate multiplicity codes on product sets. STOC (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Classification of the streaming approximability of Boolean CSPs. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. 28 (2021)
Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan
Information Spread with Error Correction. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Ideal-theoretic Explanation of Capacity-achieving Decoding. Electron. Colloquium Comput. Complex. 28 (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR (2021)
Noah Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. CoRR (2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Ideal-Theoretic Explanation of Capacity-Achieving Decoding. APPROX-RANDOM (2021)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. CoRR (2020)
Madhu Sudan, Himanshu Tyagi, Shun Watanabe
Communication for Generating Correlation: A Unifying Survey. IEEE Trans. Inf. Theory 66 (1) (2020)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Decoding Multivariate Multiplicity Codes on Product Sets. CoRR (2020)
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
Optimality of Correlated Sampling Strategies. Theory Comput. 16 (2020)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Decoding Multivariate Multiplicity Codes on Product Sets. Electron. Colloquium Comput. Complex. 27 (2020)
Noah Golowich, Madhu Sudan
Round Complexity of Common Randomness Generation: The Amortized Setting. SODA (2020)
Mitali Bafna, Srikanth Srinivasan, Madhu Sudan
Local decoding and testing of polynomials over grids. Random Struct. Algorithms 57 (3) (2020)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. CoRR (2019)
Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. SODA (2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. FOCS (2019)
Madhu Sudan, David Xiang
A Self-contained Analysis of the Lempel-Ziv Compression Algorithm. CoRR (2019)
Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
Algorithmic Polarization for Hidden Markov Models. ITCS (2019)
Noah Golowich, Madhu Sudan
Round Complexity of Common Randomness Generation: The Amortized Setting. CoRR (2019)
Madhu Sudan, Himanshu Tyagi, Shun Watanabe
Communication for Generating Correlation: A Survey. CoRR (2019)
Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
Synchronization Strings: List Decoding for Insertions and Deletions. CoRR (2018)
Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
Synchronization Strings: List Decoding for Insertions and Deletions. ICALP (2018)
Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
Polar Codes with exponentially small error at finite block length. CoRR (2018)
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
General Strong Polarization. Electron. Colloquium Comput. Complex. 25 (2018)
Srikanth Srinivasan, Madhu Sudan
Local Decoding and Testing of Polynomials over Grids. ITCS (2018)
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
General Strong Polarization. CoRR (2018)
Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
Polar Codes with Exponentially Small Error at Finite Block Length. APPROX-RANDOM (2018)
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
General strong polarization. STOC (2018)
Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
Algorithmic Polarization for Hidden Markov Models. CoRR (2018)
Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. Electron. Colloquium Comput. Complex. 25 (2018)
Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan
Communication with Contextual Uncertainty. Comput. Complex. 27 (3) (2018)
Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. CoRR (2018)
Badih Ghazi, Madhu Sudan
The Power of Shared Randomness in Uncertain Communication. CoRR (2017)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA (2017)
Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan
Compression in a Distributed Setting. ITCS (2017)
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
Sparse affine-invariant linear codes are locally testable. Comput. Complex. 26 (1) (2017)
Badih Ghazi, Madhu Sudan
The Power of Shared Randomness in Uncertain Communication. ICALP (2017)
Srikanth Srinivasan, Madhu Sudan
Local decoding and testing of polynomials over grids. CoRR (2017)
Srikanth Srinivasan, Madhu Sudan
Local decoding and testing of polynomials over grids. Electron. Colloquium Comput. Complex. 24 (2017)
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory 63 (10) (2017)
David Gamarnik, Madhu Sudan
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. SIAM J. Comput. 46 (2) (2017)
Badih Ghazi, Madhu Sudan
The Power of Shared Randomness in Uncertain Communication. Electron. Colloquium Comput. Complex. 24 (2017)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Communication Complexity of Permutation-Invariant Functions. SODA (2016)
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
The Optimality of Correlated Sampling. CoRR (2016)
Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. SODA (2016)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Decidability of Non-Interactive Simulation of Joint Distributions. Electron. Colloquium Comput. Complex. 23 (2016)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Decidability of Non-interactive Simulation of Joint Distributions. FOCS (2016)
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
The Optimality of Correlated Sampling. Electron. Colloquium Comput. Complex. 23 (2016)
Elad Haramaty, Madhu Sudan
Deterministic Compression with Uncertain Priors. Algorithmica 76 (3) (2016)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Decidability of Non-Interactive Simulation of Joint Distributions. CoRR (2016)
Alan Guo, Elad Haramaty, Madhu Sudan
Robust Testing of Lifted Codes with Applications to Low-Degree Testing. FOCS (2015)
Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. CoRR (2015)
Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication with Imperfectly Shared Randomness. ITCS (2015)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan
Streaming Lower Bounds for Approximating MAX-CUT. SODA (2015)
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA (2015)
Alan Guo, Elad Haramaty, Madhu Sudan
Robust testing of lifted codes with applications to low-degree testing. Electron. Colloquium Comput. Complex. 22 (2015)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Communication Complexity of Permutation-Invariant Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Badih Ghazi, Pritish Kamath, Madhu Sudan
Communication Complexity of Permutation-Invariant Functions. CoRR (2015)
Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. 22 (2015)
Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
Absolutely Sound Testing of Lifted Codes. Theory Comput. 11 (2015)
Elad Haramaty, Madhu Sudan
Deterministic compression with uncertain priors. ITCS (2014)
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication with Imperfectly Shared Randomness. Electron. Colloquium Comput. Complex. 21 (2014)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs. ITCS (2014)
Alan Guo, Madhu Sudan
List decoding group homomorphisms between supersolvable groups. CoRR (2014)
David Gamarnik, Madhu Sudan
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem. CoRR (2014)
Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
Optimal error rates for interactive coding I: adaptivity and other settings. STOC (2014)
Alan Guo, Madhu Sudan
List Decoding Group Homomorphisms Between Supersolvable Groups. APPROX-RANDOM (2014)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan
Approximating matching size from random streams. SODA (2014)
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. 21 (2014)
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication with Imperfectly Shared Randomness. CoRR (2014)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan
Streaming Lower Bounds for Approximating MAX-CUT. CoRR (2014)
Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. CoRR (2013)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs. Electron. Colloquium Comput. Complex. 20 (2013)
Alan Guo, Swastik Kopparty, Madhu Sudan
New affine-invariant codes from lifting. ITCS (2013)
Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
Absolutely Sound Testing of Lifted Codes. APPROX-RANDOM (2013)
Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
Absolutely Sound Testing of Lifted Codes. Electron. Colloquium Comput. Complex. 20 (2013)
Joel Spencer, Madhu Sudan, Kuang Xu
Queueing with future information. SIGMETRICS Perform. Evaluation Rev. 41 (3) (2013)
Noga Ron-Zewi, Madhu Sudan
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. Theory Comput. 9 (2013)
David Gamarnik, Madhu Sudan
Limits of local algorithms over sparse random graphs CoRR (2013)
Katalin Friedl, Madhu Sudan
Some Improvements to Total Degree Tests. CoRR (2013)
Elena Grigorescu, Tali Kaufman, Madhu Sudan
2-Transitivity is Insufficient for Local Testability. Comput. Complex. 22 (1) (2013)
Elad Haramaty, Amir Shpilka, Madhu Sudan
Optimal Testing of Multivariate Polynomials over Small Prime Fields. SIAM J. Comput. 42 (2) (2013)
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. SIAM J. Comput. 42 (6) (2013)
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
Sparse Affine-Invariant Linear Codes Are Locally Testable. FOCS (2012)
Alan Guo, Madhu Sudan
New affine-invariant codes from lifting CoRR (2012)
Elena Grigorescu, Tali Kaufman, Madhu Sudan
Succinct Representation of Codes with Applications to Testing. SIAM J. Discret. Math. 26 (4) (2012)
Noga Ron-Zewi, Madhu Sudan
A new upper bound on the query complexity for testing generalized Reed-Muller codes CoRR (2012)
Elad Haramaty, Madhu Sudan
Deterministic Compression with Uncertain Priors. Electron. Colloquium Comput. Complex. 19 (2012)
Noga Ron-Zewi, Madhu Sudan
A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. APPROX-RANDOM (2012)

Madhu Sudan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Madhu Sudan