Madhu Sudan

Orcid: 0000-0003-3718-6489

Affiliations:
  • Harvard University, School of Engineering and Applied Sciences, Boston, MA, USA
  • Microsoft Research New England, Cambridge, MA, USA


According to our database1, Madhu Sudan authored at least 194 papers between 1990 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Streaming approximation resistance of every ordering CSP.
Comput. Complex., June, 2024

Sketching Approximability of All Finite CSPs.
J. ACM, April, 2024

Local Correction of Linear Functions over the Boolean Cube.
Electron. Colloquium Comput. Complex., 2024

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers.
CoRR, 2024

Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs.
CoRR, 2024

Code Sparsification and its Applications.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Errors are Robustly Tamed in Cumulative Knowledge Processes.
Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023
An Improved Line-Point Low-Degree Test.
Electron. Colloquium Comput. Complex., 2023

Combinative Cumulative Knowledge Processes.
CoRR, 2023

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

Is This Correct? Let's Check!
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Low-Degree Testing over Grids.
Proceedings of the Approximation, 2023

2022
Point-hyperplane Incidence Geometry and the Log-rank Conjecture.
ACM Trans. Comput. Theory, 2022

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance.
IEEE Trans. Inf. Theory, 2022

Streaming beyond sketching for Maximum Directed Cut.
Electron. Colloquium Comput. Complex., 2022

Streaming complexity of CSPs with randomly ordered constraints.
Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.
Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A survey.
Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk).
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021
Linear Space Streaming Lower Bounds for Approximating CSPs.
Electron. Colloquium Comput. Complex., 2021

Approximability of all finite CSPs in the dynamic streaming setting.
Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.
Electron. Colloquium Comput. Complex., 2021

Ideal-theoretic Explanation of Capacity-achieving Decoding.
Electron. Colloquium Comput. Complex., 2021

Information Spread with Error Correction.
CoRR, 2021

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance.
Proceedings of the IEEE International Symposium on Information Theory, 2021

Approximability of all finite CSPs with linear sketches.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Optimality of Correlated Sampling Strategies.
Theory Comput., 2020

Communication for Generating Correlation: A Unifying Survey.
IEEE Trans. Inf. Theory, 2020

Local decoding and testing of polynomials over grids.
Random Struct. Algorithms, 2020

Decoding Multivariate Multiplicity Codes on Product Sets.
Electron. Colloquium Comput. Complex., 2020

Round Complexity of Common Randomness Generation: The Amortized Setting.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

Communication for Generating Correlation: A Survey.
CoRR, 2019

Algorithmic Polarization for Hidden Markov Models.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
General Strong Polarization.
Electron. Colloquium Comput. Complex., 2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.
Electron. Colloquium Comput. Complex., 2018

Communication with Contextual Uncertainty.
Comput. Complex., 2018

Synchronization Strings: List Decoding for Insertions and Deletions.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Polar Codes with Exponentially Small Error at Finite Block Length.
Proceedings of the Approximation, 2018

2017
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem.
SIAM J. Comput., 2017

Local decoding and testing of polynomials over grids.
Electron. Colloquium Comput. Complex., 2017

The Power of Shared Randomness in Uncertain Communication.
Electron. Colloquium Comput. Complex., 2017

Sparse affine-invariant linear codes are locally testable.
Comput. Complex., 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Compression in a Distributed Setting.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016
Decidability of Non-Interactive Simulation of Joint Distributions.
Electron. Colloquium Comput. Complex., 2016

The Optimality of Correlated Sampling.
Electron. Colloquium Comput. Complex., 2016

2015
Communication with Contextual Uncertainty.
Electron. Colloquium Comput. Complex., 2015

Robust testing of lifted codes with applications to low-degree testing.
Electron. Colloquium Comput. Complex., 2015

Communication Complexity of Permutation-Invariant Functions.
Electron. Colloquium Comput. Complex., 2015

Streaming Lower Bounds for Approximating MAX-CUT.
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.
Electron. Colloquium Comput. Complex., 2014

Communication with Imperfectly Shared Randomness.
Electron. Colloquium Comput. Complex., 2014

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

Optimal error rates for interactive coding I: adaptivity and other settings.
Proceedings of the Symposium on Theory of Computing, 2014

Approximating matching size from random streams.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

List Decoding Group Homomorphisms Between Supersolvable Groups.
Proceedings of the Approximation, 2014

2013
Queueing with future information.
SIGMETRICS Perform. Evaluation Rev., 2013

Optimal Testing of Multivariate Polynomials over Small Prime Fields.
SIAM J. Comput., 2013

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.
SIAM J. Comput., 2013

Absolutely Sound Testing of Lifted Codes.
Electron. Colloquium Comput. Complex., 2013

Limits of local algorithms over sparse random graphs.
Electron. Colloquium Comput. Complex., 2013

2-Transitivity is Insufficient for Local Testability.
Comput. Complex., 2013

2012
A new upper bound on the query complexity for testing generalized Reed-Muller codes.
Electron. Colloquium Comput. Complex., 2012

Deterministic Compression with Uncertain Priors.
Electron. Colloquium Comput. Complex., 2012

New affine-invariant codes from lifting.
Electron. Colloquium Comput. Complex., 2012

Some closure features of locally testable affine-invariant properties.
Electron. Colloquium Comput. Complex., 2012

New affine-invariant codes from lifting.
Electron. Colloquium Comput. Complex., 2012

Communication amid uncertainty.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011
Guest column: testing linear properties: some general theme.
SIGACT News, 2011

Derandomization of auctions.
Games Econ. Behav., 2011

Testing Linear Properties: Some general themes.
Electron. Colloquium Comput. Complex., 2011

On Sums of Locally Testable Affine Invariant Properties.
Electron. Colloquium Comput. Complex., 2011

Patterns hidden from simple algorithms: technical perspective.
Commun. ACM, 2011

Compression without a common prior: an information-theoretic justification for ambiguity in language.
Proceedings of the Innovations in Computer Science, 2011

Physical limits of Communication (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Delays and the Capacity of Continuous-Time Channels.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

From Logarithmic Advice to Single-Bit Advice.
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.
IEEE Trans. Inf. Theory, 2010

Locally Testable Codes Require Redundant Testers.
SIAM J. Comput., 2010

Invariance in Property Testing.
Electron. Colloquium Comput. Complex., 2010

Efficient Semantic Communication via Compatible Beliefs.
Electron. Colloquium Comput. Complex., 2010

Property Testing via Set-Theoretic Operations.
Electron. Colloquium Comput. Complex., 2010

Testing linear-invariant non-linear properties: A short report.
Electron. Colloquium Comput. Complex., 2010

Limits on the rate of locally testable affine-invariant codes.
Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC codes are not necessarily locally testable.
Electron. Colloquium Comput. Complex., 2010

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

Optimal Testing of Reed-Muller Codes.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Linear-Invariant Non-linear Properties: A Short Report.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Tight asymptotic bounds for the deletion channel with small deletion probabilities.
Proceedings of the IEEE International Symposium on Information Theory, 2010

2009
Succinct Representation of Codes with Applications to Testing.
Electron. Colloquium Comput. Complex., 2009

A Theory of Goal-Oriented Communication.
Electron. Colloquium Comput. Complex., 2009

Optimal testing of Reed-Muller codes.
Electron. Colloquium Comput. Complex., 2009

Probabilistically checkable proofs.
Commun. ACM, 2009

2008
Short PCPs with Polylog Query Complexity.
SIAM J. Comput., 2008

Universal Semantic Communication II: A Theory of Goal-Oriented Communication.
Electron. Colloquium Comput. Complex., 2008

Decodability of Group Homomorphisms beyond the Johnson Bound.
Electron. Colloquium Comput. Complex., 2008

Testing Linear-Invariant Non-Linear Properties.
Electron. Colloquium Comput. Complex., 2008

Algebraic algorithms and coding theory.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007
Guessing secrets efficiently via list decoding.
ACM Trans. Algorithms, 2007

Algebraic Property Testing: The Role of Invariance.
Electron. Colloquium Comput. Complex., 2007

Sparse Random Linear Codes are Locally Decodable and Testable.
Electron. Colloquium Comput. Complex., 2007

Universal Semantic Communication I.
Electron. Colloquium Comput. Complex., 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007

2006
Special Issue on Randomness and Complexity.
SIAM J. Comput., 2006

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
Networks, 2006

Robust Local Testability of Tensor Products of LDPC Codes.
Electron. Colloquium Comput. Complex., 2006

A Fuzzy Vault Scheme.
Des. Codes Cryptogr., 2006

Modelling Errors and Recovery for Communication.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Local Decoding and Testing for Homomorphisms.
Proceedings of the Approximation, 2006

2005
Distributed Computing with Imperfect Randomness.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Optimal Error Correction Against Computationally Bounded Noise.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
From logarithmic advice to single-bit advice
Electron. Colloquium Comput. Complex., 2004

Simple PCPs with Poly-log Rate and Query Complexity
Electron. Colloquium Comput. Complex., 2004

Robust Locally Testable Codes and Products of Codes
Electron. Colloquium Comput. Complex., 2004

Probabilistically checkable proofs.
Proceedings of the Computational Complexity Theory., 2004

2003
Bounds on 2-Query Codeword Testing.
Electron. Colloquium Comput. Complex., 2003

Reconstructing curves in three (and higher) dimensional space from noisy data.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Combinatorial bounds for list decoding.
IEEE Trans. Inf. Theory, 2002

Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput., 2002

Foreword.
J. Comput. Syst. Sci., 2002

Locally Testable Codes and PCPs of Almost-Linear Length
Electron. Colloquium Comput. Complex., 2002

Harmonic broadcasting is optimal.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Decoding Concatenated Codes using Soft Information.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
On representations of algebraic-geometry codes.
IEEE Trans. Inf. Theory, 2001

Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001

Linear-Consistency Testing.
J. Comput. Syst. Sci., 2001

Adversarial queuing theory.
J. ACM, 2001

Coding Theory: Tutorial and Survey.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms.
Proceedings of the Applied Algebra, 2001

Complexity classifications of Boolean constraint satisfaction problems.
SIAM monographs on discrete mathematics and applications 7, SIAM, ISBN: 978-0-89871-479-1, 2001

2000
List decoding: algorithms and applications.
SIGACT News, 2000

Gadgets, Approximation, and Linear Programming.
SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput., 2000

Small PCPs with low query complexity.
Comput. Complex., 2000

List decoding algorithms for certain concatenated codes.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Random walks with "back buttons" (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

"Soft-decision" Decoding of Chinese Remainder Codes.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

On Representations of Algebraic-Geometric Codes for List Decoding.
Proceedings of the Algorithms, 2000

1999
Improved decoding of Reed-Solomon and algebraic-geometry codes.
IEEE Trans. Inf. Theory, 1999

Computational Indistinguishability: A Sample Hierarchy.
J. Comput. Syst. Sci., 1999

Hardness of Approximating the Minimum Distance of a Linear Code
Electron. Colloquium Comput. Complex., 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
A Geometric Approach to Betweenness.
SIAM J. Discret. Math., 1998

On Syntactic versus Computational Views of Approximability.
SIAM J. Comput., 1998

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
SIAM J. Comput., 1998

Guaranteeing Fair Service to Persistent Dependent Tasks.
SIAM J. Comput., 1998

Reconstructing Algebraic Functions from Mixed Data.
SIAM J. Comput., 1998

Approximate Graph Coloring by Semidefinite Programming.
J. ACM, 1998

Private Information Retrieval.
J. ACM, 1998

Chinese Remaindering with Errors
Electron. Colloquium Comput. Complex., 1998

Learning Polynomials with Queries - The Highly Noisy Case.
Electron. Colloquium Comput. Complex., 1998

Improved decoding of Reed-Solomon and algebraic-geometric codes.
Electron. Colloquium Comput. Complex., 1998

Probabilistically checkable proofs with low amortized query complexity
Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs
Electron. Colloquium Comput. Complex., 1998

Proof verification and the hardness of approximation problems.
Electron. Colloquium Comput. Complex., 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.
Algorithmica, 1998

1997
Decoding of Reed Solomon Codes beyond the Error-Correction Bound.
J. Complex., 1997

A statistical perspective on data mining.
Future Gener. Comput. Syst., 1997

Improved low-degree testing and its applications
Electron. Colloquium Comput. Complex., 1997

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Algorithmic Issues in Coding Theory.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

1996
Linearity testing in characteristic two.
IEEE Trans. Inf. Theory, 1996

Priority encoding transmission.
IEEE Trans. Inf. Theory, 1996

Robust Characterizations of Polynomials with Applications to Program Testing.
SIAM J. Comput., 1996

Efficient Routing in Optical Networks.
J. ACM, 1996

Constraint satisfaction: The approximability of minimization problems.
Electron. Colloquium Comput. Complex., 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electron. Colloquium Comput. Complex., 1996

The Optimization Complexity of Constraint Satisfaction Problems
Electron. Colloquium Comput. Complex., 1996

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

Gadgets, Approximation, and Linear Programming (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Maximum Likelihood Decoding of Reed Solomon Codes.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Free Bits, PCP and Non-Approximability - Towards Tight Results
Electron. Colloquium Comput. Complex., 1995

Some Improvements to Total Degree Tests.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems
Lecture Notes in Computer Science 1001, Springer, ISBN: 3-540-60615-7, 1995

1994
Computing Roots of Graphs Is Hard.
Discret. Appl. Math., 1994

On-Line Algorithms for Locating Checkpoints.
Algorithmica, 1994

The minimum latency problem.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved non-approximability results.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Efficient Routing and Scheduling Algorithms for Optical Networks.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Motion Planning on a Graph (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992
Highly Resilient Correctors for Polynomials.
Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991
Self-Testing/Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990
Online Algorithms for Locating Checkpoints
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990


  Loading...