Madhu Sudan

According to our database1, Madhu Sudan authored at least 184 papers between 1990 and 2019.

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

Awards

ACM Fellow

ACM Fellow 2008, "For contributions to algorithms and complexity theory.".

IEEE Fellow

IEEE Fellow 2010, "For development of list-decoding algorithms for error-correcting codes and probabilistically-checkable proofs".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

2018
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.
Electronic Colloquium on Computational Complexity (ECCC), 2018

General strong polarization.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Local Decoding and Testing of Polynomials over Grids.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 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

(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

The Power of Shared Randomness in Uncertain Communication.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
The Optimality of Correlated Sampling.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Communication Complexity of Permutation-Invariant Functions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Communication with Contextual Uncertainty.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Decidability of Non-interactive Simulation of Joint Distributions.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Communication with Contextual Uncertainty.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Streaming Lower Bounds for Approximating MAX-CUT.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Communication with Imperfectly Shared Randomness.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Robust Testing of Lifted Codes with Applications to Low-Degree Testing.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

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

Deterministic compression with uncertain priors.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Limits of local algorithms over sparse random graphs.
Proceedings of the Innovations in Theoretical Computer Science, 2014

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

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

Queueing with future information.
SIGMETRICS Performance Evaluation Review, 2013

New affine-invariant codes from lifting.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Absolutely Sound Testing of Lifted Codes.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
A new upper bound on the query complexity for testing generalized Reed-Muller codes.
Electronic Colloquium on Computational Complexity (ECCC), 2012

New affine-invariant codes from lifting.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Some closure features of locally testable affine-invariant properties.
Electronic Colloquium on Computational Complexity (ECCC), 2012

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

Sparse Affine-Invariant Linear Codes Are Locally Testable.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

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

Testing Linear Properties: Some general themes.
Electronic Colloquium on Computational Complexity (ECCC), 2011

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

A theory of goal-oriented communication.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Efficient Semantic Communication via Compatible Beliefs.
Proceedings of the Innovations in Computer Science, 2011

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

Property Testing via Set-Theoretic Operations.
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

Optimal Testing of Multivariate Polynomials over Small Prime Fields.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Symmetric LDPC Codes are not Necessarily Locally Testable.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Limits on the Rate of Locally Testable Affine-Invariant Codes.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

On Sums of Locally Testable Affine Invariant Properties.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 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. Information Theory, 2010

Invariance in Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Testing linear-invariant non-linear properties: A short report.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Invariance in Property Testing.
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

Optimal Testing of Reed-Muller Codes.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Probabilistically checkable proofs.
Commun. ACM, 2009

Testing Linear-Invariant Non-Linear Properties.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Locally Testable Codes Require Redundant Testers.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Succinct Representation of Codes with Applications to Testing.
Proceedings of the Approximation, 2009

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

Universal Semantic Communication II: A Theory of Goal-Oriented Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Algebraic property testing: the role of invariance.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Universal semantic communication I.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Decodability of group homomorphisms beyond the johnson bound.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

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

2-Transitivity Is Insufficient for Local Testability.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007
Sparse Random Linear Codes are Locally Decodable and Testable.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 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

A Fuzzy Vault Scheme.
Des. Codes Cryptography, 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

Robust Local Testability of Tensor Products of LDPC Codes.
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

Simple PCPs with poly-log rate and query complexity.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Derandomization of auctions.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 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
Electronic Colloquium on Computational Complexity (ECCC), 2004

Simple PCPs with Poly-log Rate and Query Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust Locally Testable Codes and Products of Codes
Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electronic Colloquium on Computational Complexity (ECCC), 2004

Robust pcps of proximity, shorter pcps and applications to coding.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Robust Locally Testable Codes and Products of Codes.
Proceedings of the Approximation, 2004

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

Bounds on 2-Query Codeword Testing.
Proceedings of the Approximation, 2003

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

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

A Fuzzy Vault Scheme.
IACR Cryptology ePrint Archive, 2002

Locally Testable Codes and PCPs of Almost-Linear Length
Electronic Colloquium on Computational Complexity (ECCC), 2002

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

Guessing secrets efficiently via list decoding.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Locally Testable Codes and PCPs of Almost-Linear Length.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 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. Information Theory, 2001

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

Adversarial queuing theory.
J. ACM, 2001

Small PCPs with Low Query Complexity.
Proceedings of the STACS 2001, 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

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

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

Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC), 2000

Small PCPs with low query complexity
Electronic Colloquium on Computational Complexity (ECCC), 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

List Decoding: Algorithms and Applications.
Proceedings of the Theoretical Computer Science, 2000

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

Hardness of Approximate Hypergraph Coloring.
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. Information Theory, 1999

Hardness of Approximating the Minimum Distance of a Linear Code
Electronic Colloquium on Computational Complexity (ECCC), 1999

Linear Consistency Testing
Electronic Colloquium on Computational Complexity (ECCC), 1999

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

Chinese Remaindering with Errors.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Linear Consistency Testing.
Proceedings of the Randomization, 1999

Hardness of Approximating the Minimum Distance of a Linear Code.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

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

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

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
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

Proof Verification and the Hardness of Approximation Problems.
J. ACM, 1998

Pseudorandom generators without the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1998

Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC), 1998

Learning Polynomials with Queries - The Highly Noisy Case.
Electronic Colloquium on Computational Complexity (ECCC), 1998

Probabilistically checkable proofs with low amortized query complexity
Electronic Colloquium on Computational Complexity (ECCC), 1998

A tight characterization of NP with 3 query PCPs
Electronic Colloquium on Computational Complexity (ECCC), 1998

Computational Indistinguishability: A Sample Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1998

Proof verification and the hardness of approximation problems.
Electronic Colloquium on Computational Complexity (ECCC), 1998

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

Probabilistically Checkable Proofs with Low Amortized Query Complexity.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Tight Characterization of NP with 3 Query PCPs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Computational Indistinguishability: A Sample Hierarchy.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

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

A statistical perspective on data mining.
Future Generation Comp. Syst., 1997

Improved low-degree testing and its applications
Electronic Colloquium on Computational Complexity (ECCC), 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

Improved Low-Degree Testing and its Applications.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Gateway Based Approach for Conducting Multiparty Multimedia Sessions over Heterogeneous Signaling Domains.
Proceedings of the Proceedings IEEE INFOCOM '97, 1997

Conducting a Multiparty Multimedia Session over ATM using Hierarchically Encoded Data.
Proceedings of the 1997 IEEE International Conference on Communications: Towards the Knowledge Millennium, 1997

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

Constraint Satisfaction: The Approximability of Minimization Problems.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

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

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

Efficient Routing in Optical Networks.
J. ACM, 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Optimization Complexity of Constraint Satisfaction Problems
Electronic Colloquium on Computational Complexity (ECCC), 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
Electronic Colloquium on Computational Complexity (ECCC), 1995

Guaranteeing Fair Service to Persistent Dependent Tasks.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

A Reliable Dissemination Protocol for Interactive Collaborative Applications.
Proceedings of the Third ACM International Conference on Multimedia '95, 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

Learning Polynomials with Queries: The Highly Noisy Case.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Private Information Retrieval.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

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

Linearity Testing in Characteristic Two.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

A Geometric Approach to Betweenness.
Proceedings of the Algorithms, 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.
Discrete Applied Mathematics, 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

On Syntactic versus Computational Views of Approximability
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Approximate Graph Coloring by Semidefinite Programming
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Priority Encoding Transmission
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

Proof Verification and Hardness of Approximation Problems
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Reconstructing Algebraic Functions from Mixed Data
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 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...