Madhu Sudan
According to our database^{1},
Madhu Sudan
authored at least 184 papers
between 1990 and 2019.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2008, "For contributions to algorithms and complexity theory.".
IEEE Fellow
IEEE Fellow 2010, "For development of listdecoding algorithms for errorcorrecting codes and probabilisticallycheckable proofs".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at viaf.org

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
2019
CommunicationRounds Tradeoffs for Common Randomness and Secret Key Generation.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Algorithmic Polarization for Hidden Markov Models.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
2018
CommunicationRounds 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 NAEKSAT Problem.
SIAM J. Comput., 2017
(1 + Ω(1))Αpproximation to MAXCUT Requires Linear Space.
Proceedings of the TwentyEighth Annual ACMSIAM 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 PermutationInvariant Functions.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Communication with Contextual Uncertainty.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Decidability of Noninteractive 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 MAXCUT.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
Limitations on Testable AffineInvariant Codes in the HighRate Regime.
Proceedings of the TwentySixth Annual ACMSIAM 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 LowDegree 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 TwentyFifth Annual ACMSIAM 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 ReedMuller Codes.
Theory of Computing, 2013
Queueing with future information.
SIGMETRICS Performance Evaluation Review, 2013
New affineinvariant 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 ReedMuller codes.
Electronic Colloquium on Computational Complexity (ECCC), 2012
New affineinvariant codes from lifting.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Some closure features of locally testable affineinvariant properties.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Communication amid uncertainty.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012
Sparse AffineInvariant 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 ReedMuller 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 goaloriented 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 informationtheoretic justification for ambiguity in language.
Proceedings of the Innovations in Computer Science, 2011
Property Testing via SetTheoretic 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 ContinuousTime 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 AffineInvariant 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 SingleBit 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 linearinvariant nonlinear 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 LinearInvariant Nonlinear 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 ReedMuller Codes.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
2009
Probabilistically checkable proofs.
Commun. ACM, 2009
Testing LinearInvariant NonLinear 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 GoalOriented 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
2Transitivity 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 ComplexityTheoretic 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 bandwidthoptimal 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 polylog 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 singlebit advice
Electronic Colloquium on Computational Complexity (ECCC), 2004
Simple PCPs with Polylog 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
Randomnessefficient low degree tests and short PCPs via epsilonbiased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Bounds on 2Query 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 AlmostLinear Length
Electronic Colloquium on Computational Complexity (ECCC), 2002
Harmonic broadcasting is optimal.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Guessing secrets efficiently via list decoding.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Locally Testable Codes and PCPs of AlmostLinear 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 algebraicgeometry 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 ErrorCorrecting Codes: Unifying Algebraic and NumberTheoretic 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 ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
Random walks with "back buttons" (extended abstract).
Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
List Decoding: Algorithms and Applications.
Proceedings of the Theoretical Computer Science, 2000
"Softdecision" 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 AlgebraicGeometric Codes for List Decoding.
Proceedings of the Algorithms, 2000
1999
Improved decoding of ReedSolomon and algebraicgeometry 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 ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Chinese Remaindering with Errors.
Proceedings of the ThirtyFirst 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 NonapproximabilityTowards 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 ReedSolomon and AlgebraicGeometric 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 ErrorCorrection Bound.
J. Complexity, 1997
A statistical perspective on data mining.
Future Generation Comp. Syst., 1997
Improved lowdegree 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 TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Improved LowDegree Testing and its Applications.
Proceedings of the TwentyNinth 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 TwentyEighth 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 NonApproximability  Towards Tight Results
Electronic Colloquium on Computational Complexity (ECCC), 1995
Guaranteeing Fair Service to Persistent Dependent Tasks.
Proceedings of the Sixth Annual ACMSIAM 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 MultiCuts 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 NonApproximability  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: 3540606157, 1995
1994
Computing Roots of Graphs Is Hard.
Discrete Applied Mathematics, 1994
OnLine Algorithms for Locating Checkpoints.
Algorithmica, 1994
The minimum latency problem.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Improved nonapproximability results.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Efficient Routing and Scheduling Algorithms for Optical Networks.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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
SelfTesting Polynomial Functions Efficiently and Over Rational Domains.
Proceedings of the Third Annual ACM/SIGACTSIAM 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
SelfTesting/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