Madhu Sudan

According to our database, Madhu Sudan authored at least 191 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2024

Sketching Approximability of All Finite CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

J. ACM, April, 2024

Local Correction of Linear Functions over the Boolean Cube.

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

Electron. Colloquium Comput. Complex., 2024

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs.

Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan

CoRR, 2024

Code Sparsification and its Applications.

Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

An Improved Line-Point Low-Degree Test.

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

Electron. Colloquium Comput. Complex., 2023

Combinative Cumulative Knowledge Processes.

Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan

CoRR, 2023

On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction.

Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu

CoRR, 2023

Is This Correct? Let's Check!

Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Low-Degree Testing over Grids.

Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan

Proceedings of the Approximation, 2023

2022

Point-hyperplane Incidence Geometry and the Log-rank Conjecture.

Noah Singer, Madhu Sudan

ACM Trans. Comput. Theory, 2022

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance.

Elena Grigorescu, Madhu Sudan, Minshen Zhu

IEEE Trans. Inf. Theory, 2022

General Strong Polarization.

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

J. ACM, 2022

Streaming beyond sketching for Maximum Directed Cut.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Streaming complexity of CSPs with randomly ordered constraints.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A survey.

Madhu Sudan

Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk).

Madhu Sudan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Streaming approximation resistance of every ordering CSP.

Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Linear Space Streaming Lower Bounds for Approximating CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Approximability of all finite CSPs in the dynamic streaming setting.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2021

Ideal-theoretic Explanation of Capacity-achieving Decoding.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Electron. Colloquium Comput. Complex., 2021

Information Spread with Error Correction.

Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan

CoRR, 2021

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance.

Elena Grigorescu, Madhu Sudan, Minshen Zhu

Proceedings of the IEEE International Symposium on Information Theory, 2021

Approximability of all finite CSPs with linear sketches.

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Optimality of Correlated Sampling Strategies.

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan

Theory Comput., 2020

Communication for Generating Correlation: A Unifying Survey.

Madhu Sudan, Himanshu Tyagi, Shun Watanabe

IEEE Trans. Inf. Theory, 2020

Local decoding and testing of polynomials over grids.

Mitali Bafna, Srikanth Srinivasan, Madhu Sudan

Random Struct. Algorithms, 2020

Decoding Multivariate Multiplicity Codes on Product Sets.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Electron. Colloquium Comput. Complex., 2020

Round Complexity of Common Randomness Generation: The Amortized Setting.

Noah Golowich, Madhu Sudan

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

A Self-contained Analysis of the Lempel-Ziv Compression Algorithm.

Madhu Sudan, David Xiang

CoRR, 2019

Communication for Generating Correlation: A Survey.

Madhu Sudan, Himanshu Tyagi, Shun Watanabe

CoRR, 2019

Algorithmic Polarization for Hidden Markov Models.

Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

Electron. Colloquium Comput. Complex., 2018

Communication with Contextual Uncertainty.

Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan

Comput. Complex., 2018

Synchronization Strings: List Decoding for Insertions and Deletions.

Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Polar Codes with Exponentially Small Error at Finite Block Length.

Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan

Proceedings of the Approximation, 2018

2017

Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem.

David Gamarnik, Madhu Sudan

SIAM J. Comput., 2017

Local decoding and testing of polynomials over grids.

Srikanth Srinivasan, Madhu Sudan

Electron. Colloquium Comput. Complex., 2017

The Power of Shared Randomness in Uncertain Communication.

Badih Ghazi, Madhu Sudan

Electron. Colloquium Comput. Complex., 2017

Sparse affine-invariant linear codes are locally testable.

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

Comput. Complex., 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Compression in a Distributed Setting.

Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Decidability of Non-Interactive Simulation of Joint Distributions.

Badih Ghazi, Pritish Kamath, Madhu Sudan

Electron. Colloquium Comput. Complex., 2016

The Optimality of Correlated Sampling.

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan

Electron. Colloquium Comput. Complex., 2016

Deterministic Compression with Uncertain Priors.

Elad Haramaty, Madhu Sudan

Algorithmica, 2016

2015

Absolutely Sound Testing of Lifted Codes.

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

Theory Comput., 2015

Communication with Contextual Uncertainty.

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

Electron. Colloquium Comput. Complex., 2015

Robust testing of lifted codes with applications to low-degree testing.

Alan Guo, Elad Haramaty, Madhu Sudan

Electron. Colloquium Comput. Complex., 2015

Communication Complexity of Permutation-Invariant Functions.

Badih Ghazi, Pritish Kamath, Madhu Sudan

Electron. Colloquium Comput. Complex., 2015

Streaming Lower Bounds for Approximating MAX-CUT.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Electron. Colloquium Comput. Complex., 2014

Communication with Imperfectly Shared Randomness.

Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2014

Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem.

David Gamarnik, Madhu Sudan

CoRR, 2014

Optimal error rates for interactive coding I: adaptivity and other settings.

Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan

Proceedings of the Symposium on Theory of Computing, 2014

Approximating matching size from random streams.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

List Decoding Group Homomorphisms Between Supersolvable Groups.

Alan Guo, Madhu Sudan

Proceedings of the Approximation, 2014

2013

A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes.

Noga Ron-Zewi, Madhu Sudan

Theory Comput., 2013

Queueing with future information.

Joel Spencer, Madhu Sudan, Kuang Xu

SIGMETRICS Perform. Evaluation Rev., 2013

Limits of local algorithms over sparse random graphs.

David Gamarnik, Madhu Sudan

Electron. Colloquium Comput. Complex., 2013

2-Transitivity is Insufficient for Local Testability.

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Comput. Complex., 2013

2012

Succinct Representation of Codes with Applications to Testing.

Elena Grigorescu, Tali Kaufman, Madhu Sudan

SIAM J. Discret. Math., 2012

A theory of goal-oriented communication.

Oded Goldreich, Brendan Juba, Madhu Sudan

J. ACM, 2012

New affine-invariant codes from lifting.

Alan Guo, Madhu Sudan

Electron. Colloquium Comput. Complex., 2012

Some closure features of locally testable affine-invariant properties.

Alan Guo, Madhu Sudan

Electron. Colloquium Comput. Complex., 2012

New affine-invariant codes from lifting.

Alan Guo, Swastik Kopparty, Madhu Sudan

Electron. Colloquium Comput. Complex., 2012

Communication amid uncertainty.

Madhu Sudan

Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011

Testing Linear-Invariant Non-Linear Properties.

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Theory Comput., 2011

Guest column: testing linear properties: some general theme.

Madhu Sudan

SIGACT News, 2011

Derandomization of auctions.

Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan

Games Econ. Behav., 2011

Testing Linear Properties: Some general themes.

Madhu Sudan

Electron. Colloquium Comput. Complex., 2011

Optimal testing of multivariate polynomials over small prime fields.

Elad Haramaty, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2011

On Sums of Locally Testable Affine Invariant Properties.

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2011

Patterns hidden from simple algorithms: technical perspective.

Madhu Sudan

Commun. ACM, 2011

Compression without a common prior: an information-theoretic justification for ambiguity in language.

Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan

Proceedings of the Innovations in Computer Science, 2011

Physical limits of Communication (Invited Talk).

Madhu Sudan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Delays and the Capacity of Continuous-Time Channels.

Sanjeev Khanna, Madhu Sudan

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

From Logarithmic Advice to Single-Bit Advice.

Oded Goldreich, Madhu Sudan, Luca Trevisan

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

Optimal Error Correction for Computationally Bounded Noise.

Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson

IEEE Trans. Inf. Theory, 2010

Invariance in Property Testing.

Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

Efficient Semantic Communication via Compatible Beliefs.

Brendan Juba, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

Property Testing via Set-Theoretic Operations.

Victor Chen, Madhu Sudan, Ning Xie

Electron. Colloquium Comput. Complex., 2010

Testing linear-invariant non-linear properties: A short report.

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Electron. Colloquium Comput. Complex., 2010

Limits on the rate of locally testable affine-invariant codes.

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC codes are not necessarily locally testable.

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

Invariance in Property Testing.

Madhu Sudan

Proceedings of the Property Testing - Current Research and Surveys, 2010

Optimal Testing of Reed-Muller Codes.

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Linear-Invariant Non-linear Properties: A Short Report.

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Proceedings of the Property Testing - Current Research and Surveys, 2010

Tight asymptotic bounds for the deletion channel with small deletion probabilities.

Adam Kalai, Michael Mitzenmacher, Madhu Sudan

Proceedings of the IEEE International Symposium on Information Theory, 2010

2009

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers.

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Electron. Colloquium Comput. Complex., 2009

Optimal testing of Reed-Muller codes.

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Electron. Colloquium Comput. Complex., 2009

Locally Testable Codes Require Redundant Testers.

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Electron. Colloquium Comput. Complex., 2009

Probabilistically checkable proofs.

Madhu Sudan

Commun. ACM, 2009

2008

Short PCPs with Polylog Query Complexity.

Eli Ben-Sasson, Madhu Sudan

SIAM J. Comput., 2008

Universal Semantic Communication II: A Theory of Goal-Oriented Communication.

Brendan Juba, Madhu Sudan

Electron. Colloquium Comput. Complex., 2008

Decodability of Group Homomorphisms beyond the Johnson Bound.

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Electron. Colloquium Comput. Complex., 2008

Algebraic algorithms and coding theory.

Madhu Sudan

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007

Guessing secrets efficiently via list decoding.

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan

ACM Trans. Algorithms, 2007

Algebraic Property Testing: The Role of Invariance.

Tali Kaufman, Madhu Sudan

Electron. Colloquium Comput. Complex., 2007

Sparse Random Linear Codes are Locally Decodable and Testable.

Tali Kaufman, Madhu Sudan

Electron. Colloquium Comput. Complex., 2007

Universal Semantic Communication I.

Brendan Juba, Madhu Sudan

Electron. Colloquium Comput. Complex., 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.

Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee

Proceedings of the Advances in Cryptology, 2007

2006

Special Issue on Randomness and Complexity.

Oded Goldreich, Madhu Sudan

SIAM J. Comput., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.

Lars Engebretsen, Madhu Sudan

Networks, 2006

Locally testable codes and PCPs of almost-linear length.

Oded Goldreich, Madhu Sudan

J. ACM, 2006

Robust Local Testability of Tensor Products of LDPC Codes.

Irit Dinur, Madhu Sudan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2006

A Fuzzy Vault Scheme.

Ari Juels, Madhu Sudan

Des. Codes Cryptogr., 2006

Modelling Errors and Recovery for Communication.

Madhu Sudan

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Local Decoding and Testing for Homomorphisms.

Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Proceedings of the Approximation, 2006

2005

Distributed Computing with Imperfect Randomness.

Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan

Proceedings of the Distributed Computing, 19th International Conference, 2005

Optimal Error Correction Against Computationally Bounded Noise.

Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson

Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Short PCPs Verifiable in Polylogarithmic Time.

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

From logarithmic advice to single-bit advice

Oded Goldreich, Madhu Sudan, Luca Trevisan

Electron. Colloquium Comput. Complex., 2004

Simple PCPs with Poly-log Rate and Query Complexity

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2004

Robust Locally Testable Codes and Products of Codes

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2004

Probabilistically checkable proofs.

Madhu Sudan

Proceedings of the Computational Complexity Theory., 2004

2003

Bounds on 2-Query Codeword Testing.

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Electron. Colloquium Comput. Complex., 2003

Improved Low-Degree Testing and its Applications.

Sanjeev Arora, Madhu Sudan

Comb., 2003

Reconstructing curves in three (and higher) dimensional space from noisy data.

Don Coppersmith, Madhu Sudan

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.

Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Combinatorial bounds for list decoding.

Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman

IEEE Trans. Inf. Theory, 2002

Foreword.

Madhu Sudan

J. Comput. Syst. Sci., 2002

Harmonic broadcasting is optimal.

Lars Engebretsen, Madhu Sudan

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Decoding Concatenated Codes using Soft Information.

Venkatesan Guruswami, Madhu Sudan

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

On representations of algebraic-geometry codes.

Venkatesan Guruswami, Madhu Sudan

IEEE Trans. Inf. Theory, 2001

Pseudorandom Generators without the XOR Lemma.

Madhu Sudan, Luca Trevisan, Salil P. Vadhan

J. Comput. Syst. Sci., 2001

Linear-Consistency Testing.

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan

J. Comput. Syst. Sci., 2001

Adversarial queuing theory.

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson

J. ACM, 2001

Coding Theory: Tutorial and Survey.

Madhu Sudan

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms.

Madhu Sudan

Proceedings of the Applied Algebra, 2001

Complexity classifications of Boolean constraint satisfaction problems.

Nadia Creignou, Sanjeev Khanna, Madhu Sudan

SIAM monographs on discrete mathematics and applications 7, SIAM, ISBN: 978-0-89871-479-1, 2001

2000

List decoding: algorithms and applications.

Madhu Sudan

SIGACT News, 2000

Learning Polynomials with Queries: The Highly Noisy Case.

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

SIAM J. Discret. Math., 2000

Gadgets, Approximation, and Linear Programming.

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson

SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson

SIAM J. Comput., 2000

Hardness of approximate hypergraph coloring

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

Electron. Colloquium Comput. Complex., 2000

Small PCPs with low query complexity.

Prahladh Harsha, Madhu Sudan

Comput. Complex., 2000

List decoding algorithms for certain concatenated codes.

Venkatesan Guruswami, Madhu Sudan

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Random walks with "back buttons" (extended abstract).

Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

"Soft-decision" Decoding of Chinese Remainder Codes.

Venkatesan Guruswami, Amit Sahai, Madhu Sudan

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

On Representations of Algebraic-Geometric Codes for List Decoding.

Venkatesan Guruswami, Madhu Sudan

Proceedings of the Algorithms, 2000

1999

Improved decoding of Reed-Solomon and algebraic-geometry codes.

Venkatesan Guruswami, Madhu Sudan

IEEE Trans. Inf. Theory, 1999

Computational Indistinguishability: A Sample Hierarchy.

Oded Goldreich, Madhu Sudan

J. Comput. Syst. Sci., 1999

Hardness of Approximating the Minimum Distance of a Linear Code

Ilya Dumer, Daniele Micciancio, Madhu Sudan

Electron. Colloquium Comput. Complex., 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).

Madhu Sudan, Luca Trevisan, Salil P. Vadhan

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).

Madhu Sudan, Luca Trevisan, Salil P. Vadhan

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Geometric Approach to Betweenness.

Benny Chor, Madhu Sudan

SIAM J. Discret. Math., 1998

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.

Mihir Bellare, Oded Goldreich, Madhu Sudan

SIAM J. Comput., 1998

Guaranteeing Fair Service to Persistent Dependent Tasks.

Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan

SIAM J. Comput., 1998

Reconstructing Algebraic Functions from Mixed Data.

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan

SIAM J. Comput., 1998

Approximate Graph Coloring by Semidefinite Programming.

David R. Karger, Rajeev Motwani, Madhu Sudan

J. ACM, 1998

Private Information Retrieval.

Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan

J. ACM, 1998

Proof Verification and the Hardness of Approximation Problems.

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

J. ACM, 1998

Chinese Remaindering with Errors

Oded Goldreich, Dana Ron, Madhu Sudan

Electron. Colloquium Comput. Complex., 1998

Improved decoding of Reed-Solomon and algebraic-geometric codes.

Venkatesan Guruswami, Madhu Sudan

Electron. Colloquium Comput. Complex., 1998

Probabilistically checkable proofs with low amortized query complexity

Madhu Sudan, Luca Trevisan

Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan

Electron. Colloquium Comput. Complex., 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan

Algorithmica, 1998

1997

Decoding of Reed Solomon Codes beyond the Error-Correction Bound.

Madhu Sudan

J. Complex., 1997

A statistical perspective on data mining.

Jonathan R. M. Hosking, Edwin P. D. Pednault, Madhu Sudan

Future Gener. Comput. Syst., 1997

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.

Sanjeev Khanna, Madhu Sudan, David P. Williamson

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Algorithmic Issues in Coding Theory.

Madhu Sudan

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

1996

Linearity testing in characteristic two.

Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan

IEEE Trans. Inf. Theory, 1996

Priority encoding transmission.

Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan

IEEE Trans. Inf. Theory, 1996

Robust Characterizations of Polynomials with Applications to Program Testing.

Ronitt Rubinfeld, Madhu Sudan

SIAM J. Comput., 1996

Efficient Routing in Optical Networks.

Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan

J. ACM, 1996

Constraint satisfaction: The approximability of minimization problems.

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Electron. Colloquium Comput. Complex., 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

Sanjeev Khanna, Madhu Sudan, David P. Williamson

Electron. Colloquium Comput. Complex., 1996

The Optimization Complexity of Constraint Satisfaction Problems

Sanjeev Khanna, Madhu Sudan

Electron. Colloquium Comput. Complex., 1996

Adversarial Queueing Theory.

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Gadgets, Approximation, and Linear Programming (extended abstract).

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Maximum Likelihood Decoding of Reed Solomon Codes.

Madhu Sudan

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Free Bits, PCP and Non-Approximability - Towards Tight Results

Mihir Bellare, Oded Goldreich, Madhu Sudan

Electron. Colloquium Comput. Complex., 1995

On Syntactic versus Computational Views of Approximability

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani

Electron. Colloquium Comput. Complex., 1995

Some Improvements to Total Degree Tests.

Katalin Friedl, Madhu Sudan

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan

Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.

Mihir Bellare, Oded Goldreich, Madhu Sudan

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems

Madhu Sudan

Lecture Notes in Computer Science 1001, Springer, ISBN: 3-540-60615-7, 1995

1994

Computing Roots of Graphs Is Hard.

Rajeev Motwani, Madhu Sudan

Discret. Appl. Math., 1994

On-Line Algorithms for Locating Checkpoints.

Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan

Algorithmica, 1994

The minimum latency problem.

Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved non-approximability results.

Mihir Bellare, Madhu Sudan

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Efficient Routing and Scheduling Algorithms for Optical Networks.

Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Motion Planning on a Graph (Extended Abstract)

Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992

Highly Resilient Correctors for Polynomials.

Peter Gemmell, Madhu Sudan

Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.

Ronitt Rubinfeld, Madhu Sudan

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

Self-Testing/Correcting for Polynomials and for Approximate Functions

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

Online Algorithms for Locating Checkpoints

Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990