Madhu Sudan
#8,055
Most Influential Person Now
Indian computer scientist
Madhu Sudan's AcademicInfluence.com Rankings
Madhu Sudancomputer-science Degrees
Computer Science
#486
World Rank
#504
Historical Rank
Database
#1487
World Rank
#1562
Historical Rank
Download Badge
Computer Science
Madhu Sudan's Degrees
- PhD Computer Science University of California, Berkeley
Similar Degrees You Can Earn
Why Is Madhu Sudan Influential?
(Suggest an Edit or Addition)According to Wikipedia, Madhu Sudan is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015. Career He received his bachelor's degree in computer science from IIT Delhi in 1987 and his doctoral degree in computer science at the University of California, Berkeley in 1992. He was a research staff member at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York from 1992 to 1997 and moved to MIT after that. From 2009 to 2015 he was a permanent researcher at Microsoft Research New England before joining Harvard University in 2015.
Madhu Sudan's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Private information retrieval (1995) (2485)
- Proof verification and hardness of approximation problems (1992) (2163)
- A Fuzzy Vault Scheme (2002) (1568)
- Improved decoding of Reed-Solomon and algebraic-geometric codes (1998) (1213)
- Decoding of Reed Solomon Codes beyond the Error-Correction Bound (1997) (789)
- Robust Characterizations of Polynomials with Applications to Program Testing (1996) (769)
- Priority encoding transmission (1994) (705)
- Free bits, PCPs and non-approximability-towards tight results (1995) (613)
- Approximate graph coloring by semidefinite programming (1994) (557)
- Complexity classifications of Boolean constraint satisfaction problems (2001) (428)
- Pseudorandom generators without the XOR Lemma (1999) (408)
- A reliable dissemination protocol for interactive collaborative applications (1995) (382)
- The minimum latency problem (1994) (340)
- On syntactic versus computational views of approximability (1994) (304)
- Robust pcps of proximity, shorter pcps and applications to coding (2004) (290)
- Improved Low-Degree Testing and its Applications (1997) (286)
- Gadgets, approximation, and linear programming (1996) (284)
- Approximating Minimum Feedback Sets and Multicuts in Directed Graphs (1998) (284)
- Adversarial queuing theory (2001) (257)
- Chinese remaindering with errors (1999) (212)
- The Approximability of Constraint Satisfaction Problems (2001) (212)
- Self-testing/correcting for polynomials and for approximate functions (1991) (210)
- Locally testable codes and PCPs of almost-linear length (2002) (190)
- Linearity testing in characteristic two (1995) (188)
- Adversarial queueing theory (1996) (188)
- Improved non-approximability results (1994) (184)
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers (2009) (182)
- Learning polynomials with queries: The highly noisy case (1995) (178)
- Efficient routing and scheduling algorithms for optical networks (1994) (163)
- Highly Resilient Correctors for Polynomials (1992) (161)
- Short PCPs with Polylog Query Complexity (2008) (160)
- Algebraic property testing: the role of invariance (2008) (145)
- Hardness of approximating the minimum distance of a linear code (1999) (141)
- List decoding: algorithms and applications (2000) (131)
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets (2003) (131)
- Limits of local algorithms over sparse random graphs (2013) (129)
- Short PCPs verifiable in polylogarithmic time (2005) (116)
- A Geometric Approach to Betweenness (1995) (112)
- Combinatorial bounds for list decoding (2002) (99)
- Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs (1995) (98)
- Approximating matching size from random streams (2014) (96)
- Maximum-likelihood decoding of Reed-Solomon codes is NP-hard (1996) (92)
- List decoding algorithms for certain concatenated codes (2000) (91)
- Some improvements to total degree tests (1995) (91)
- A statistical perspective on data mining (1997) (89)
- New affine-invariant codes from lifting (2012) (89)
- Efficient routing in optical networks (1996) (86)
- Computing Roots of Graphs Is Hard (1994) (86)
- Optimal Testing of Reed-Muller Codes (2009) (83)
- Robust locally testable codes and products of codes (2004) (81)
- Reconstructing algebraic functions from mixed data (1992) (79)
- Reconstructing curves in three (and higher) dimensional space from noisy data (2003) (78)
- A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction (1997) (77)
- Hardness of approximate hypergraph coloring (2000) (76)
- A tight characterization of NP with 3 query PCPs (1998) (75)
- Optimal Error Correction Against Computationally Bounded Noise (2005) (74)
- Optimal error rates for interactive coding I: adaptivity and other settings (2013) (73)
- "Soft-decision" decoding of Chinese remainder codes (2000) (70)
- Motion planning on a graph (1994) (69)
- Simple PCPs with poly-log rate and query complexity (2005) (67)
- Self-testing polynomial functions efficiently and over rational domains (1992) (66)
- Constraint satisfaction: the approximability of minimization problems (1997) (65)
- Derandomization of auctions (2005) (64)
- Random walks with `back buttons' (2001) (62)
- Improved lower bound on the size of Kakeya sets over finite fields (2008) (57)
- Computational applications of noise sensitivity (2003) (57)
- Robust Local Testability of Tensor Products of LDPC Codes (2006) (56)
- Tight asymptotic bounds for the deletion channel with small deletion probabilities (2010) (55)
- Pseudorandom generators without the XOR Lemma (extended abstract) (1999) (55)
- Sparse Random Linear Codes are Locally Decodable and Testable (2007) (51)
- A theory of goal-oriented communication (2012) (49)
- Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2007) (46)
- Streaming Lower Bounds for Approximating MAX-CUT (2014) (45)
- Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time (2019) (45)
- Efficient Checking of Polynomials and Proofs and the Hardness of Appoximation Problems (1995) (43)
- Guaranteeing fair service to persistent dependent tasks (1995) (43)
- Extensions to the Johnson bound (2001) (42)
- Invariance in Property Testing (2010) (41)
- Small PCPs with low query complexity (2000) (39)
- Synchronization Strings: List Decoding for Insertions and Deletions (2018) (37)
- Morphological Variations and Biometrics of Ear: An Aid to Personal Identification. (2016) (35)
- Testing Linear-Invariant Non-Linear Properties (2008) (34)
- Hardness of approximating the minimum distance of a linear code (2000) (33)
- Locally Testable Codes Require Redundant Testers (2009) (32)
- Communication With Imperfectly Shared Randomness (2014) (32)
- Compression without a common prior: an information-theoretic justification for ambiguity in language (2011) (32)
- Probabilistically checkable proofs with low amortized query complexity (1998) (31)
- Succinct Representation of Codes with Applications to Testing (2009) (31)
- Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem (2017) (31)
- On Dinur’s proof of the PCP theorem (2006) (30)
- Guessing secrets efficiently via list decoding (2002) (30)
- 2-Transitivity is Insufficient for Local Testability (2008) (30)
- Robust Characterizations of Polynomials and Their Applications to Program Testing (1993) (30)
- Limits on the Rate of Locally Testable Affine-Invariant Codes (2011) (30)
- Decidability of Non-interactive Simulation of Joint Distributions (2016) (29)
- Coding Theory: Tutorial and Survey (2001) (29)
- Harmonic broadcasting is bandwidth‐optimal assuming constant bit rate (2006) (29)
- A daylight factor model under clear sky conditions for building: An experimental validation (2015) (29)
- Symmetric LDPC Codes are not Necessarily Locally Testable (2011) (29)
- Decoding Reed Solomon Codes beyond the Error-Correction Diameter (1997) (28)
- (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space (2017) (28)
- On representations of algebraic-geometry codes (2001) (27)
- General strong polarization (2018) (26)
- Bounds on 2-Query Codeword Testing (2003) (25)
- Queuing with future information (2012) (25)
- Harmonic broadcasting is optimal (2002) (24)
- Communication for Generating Correlation: A Unifying Survey (2019) (24)
- Optimal Testing of Multivariate Polynomials over Small Prime Fields (2011) (23)
- Random walks with “back buttons” (extended abstract) (2000) (23)
- Probabilistically checkable proofs (2009) (23)
- Universal Semantic Communication II: A Theory of Goal-Oriented Communication (2008) (22)
- Open Problems in Data Streams, Property Testing, and Related Topics (2011) (21)
- Queueing with future information (2014) (20)
- Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms (2001) (20)
- Coding theory: tutorial & survey (2001) (20)
- On Sums of Locally Testable Affine Invariant Properties (2011) (20)
- 3. Boolean Constraint Satisfaction Problems (2001) (20)
- Distributed Computing with Imperfect Randomness (2005) (19)
- Decodability of group homomorphisms beyond the johnson bound (2008) (18)
- From logarithmic advice to single-bit advice (2004) (18)
- Decoding concatenated codes using soft information (2002) (17)
- Optimal Error Correction for Computationally Bounded Noise (2010) (16)
- Daylighting and energy performance of a building for composite climate: An experimental study (2016) (16)
- Efficient Semantic Communication via Compatible Beliefs (2010) (16)
- Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem (2014) (16)
- Gadgets, Approximation, and Linear Programming (extended abstract). (1996) (15)
- The Optimization Complexity of Constraint Satisfaction Problems (1995) (14)
- Linear Consistency Testing (1999) (14)
- Tomographic and volumetric reconstruction of composite materials using full-field swept-source optical coherence tomography (2012) (14)
- Deterministic Compression with Uncertain Priors (2012) (14)
- The Optimality of Correlated Sampling (2016) (13)
- Kakeya-type sets in finite vector spaces (2010) (13)
- Motion Planning on a Graph (Extended Abstract) (1994) (13)
- Testing Linear-Invariant Non-linear Properties: A Short Report (2010) (13)
- Dynamic analysis of daylight metrics and energy saving for rooftop window integrated flat roof structure of building (2015) (13)
- Computational indistinguishability: a sample hierarchy (1998) (13)
- Robust pcps of proximity and shorter pcps (2004) (13)
- Polar Codes with Exponentially Small Error at Finite Block Length (2018) (13)
- Energy matrices of the building by incorporating daylight concept for composite climate—An experimental study (2014) (12)
- Climate-Based Daylight Modeling (CBDM) for an atrium: An experimentally validated novel daylight performance (2017) (12)
- The P vs. NP problem (2010) (12)
- Local Decoding and Testing for Homomorphisms (2006) (11)
- Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance (2020) (11)
- Sparse affine-invariant linear codes are locally testable (2012) (11)
- Algorithmic Issues in Coding Theory (1997) (11)
- Linear space streaming lower bounds for approximating CSPs (2021) (10)
- Connectivity Properties of Matroids (1992) (10)
- Absolutely Sound Testing of Lifted Codes (2013) (10)
- Advances in Software Engineering Techniques (2009) (9)
- Property Testing via Set-Theoretic Operations (2010) (9)
- Communication Complexity of Permutation-Invariant Functions (2015) (9)
- FIRST RECORD OF PARACOCCUS MARGINATUS ( HEMIPTERA : PSEUDOCOCCIDAE ) , AN INVASIVE ALIEN SPECIES ON PAPAYA ( CARICA PAPAYA L . ) IN JAMMU ( J & K ) , INDIA (2013) (9)
- Reections on \Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes" (2002) (8)
- Studies on the Effect of Photoperiodism and Temperature on Moulting of a Freshwater Prawn Macrobrachium dayanum (2015) (8)
- Communication with Contextual Uncertainty (2015) (8)
- Pseudorandom Generators without the XOR Lemma (Abstract). (1999) (8)
- Approximability of all finite CSPs with linear sketches (2021) (7)
- Gateway based approach for conducting multiparty multimedia sessions over heterogeneous signaling domains (1997) (7)
- Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation (2018) (7)
- Online algorithms for locating checkpoints (1990) (7)
- Maximum likelihood decoding of Reed Solomon codes (1996) (7)
- Robust Testing of Lifted Codes with Applications to Low-Degree Testing (2015) (7)
- Evaluation of sexual dimorphism using permanent maxillary first molar in Sri Ganganagar population (2017) (7)
- Guest column: testing linear properties: some general theme (2011) (6)
- The Power of Shared Randomness in Uncertain Communication (2017) (6)
- A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes (2012) (6)
- Approximability of all finite CSPs in the dynamic streaming setting (2021) (6)
- Approximability of all Boolean CSPs in the dynamic streaming setting∗ (2021) (6)
- A theory of goal-oriented communication (2011) (5)
- On-line algorithms for locating checkpoints (2005) (5)
- A REPORT ON THE OCCURRENCE OF INSECT PESTS ON ZANTHOXYLUM ARMATUM DC. (FAMILY: RUTACEAE), AN IMPORTANT MEDICINAL PLANT IN JAMMU REGION (2011) (5)
- List decoding group homomorphisms between supersolvable groups (2014) (5)
- On Representations of Algebraic-Geometric Codes (1998) (5)
- Streaming approximation resistance of every ordering CSP (2021) (5)
- Approximability of all Boolean CSPs with linear sketches (2021) (5)
- Insect pests infesting Calotropis procera (Ait.) Ait. F. (Asclepiadaceae), a medicinal plant in district Rajouri of Jammu region (J&K). (2011) (4)
- On Representations of Algebraic-Geometric Codes for List Decoding (2000) (4)
- A Crash Course on Coding Theory (2001) (4)
- Effect of photoperiod and temperature on development and growth of hepatopancreas of freshwater prawn Macrobrachium dayanum (2015) (4)
- Essential Coding Theory Problem Set 2 (4)
- Testing Linear Properties: Some general themes (2011) (3)
- Communication for Generating Correlation: A Survey (2019) (3)
- Some closure features of locally testable affine-invariant properties (2012) (3)
- On the role of algebra in the efficient verification of proofs (1994) (3)
- Confidentiality-Preserving Query Execution of Fragmented Outsourced Data (2018) (3)
- Complexity Theory Column 34 (2007) (3)
- Conducting a multiparty multimedia session over ATM: using hierarchically encoded data (1997) (3)
- Algorithmic Polarization for Hidden Markov Models (2018) (3)
- Streaming and Sketching Complexity of CSPs: A survey (2022) (2)
- Round Complexity of Common Randomness Generation: The Amortized Setting (2019) (2)
- Pseudorandom generators without the XOR lemma (1999) (2)
- Limitations on Testable Affine-Invariant Codes in the High-Rate Regime (2015) (2)
- Classification of the streaming approximability of Boolean CSPs (2021) (2)
- The Optimization Complexity of Structure Maximization Problems (1996) (2)
- Optimality of Correlated Sampling Strategies (2016) (2)
- Sketching Approximability of (Weak) Monarchy Predicates (2022) (2)
- Point-hyperplane Incidence Geometry and the Log-rank Conjecture (2021) (2)
- Communication amid uncertainty (2012) (2)
- Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (2016) (2)
- A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction (1996) (2)
- Hardness of approximations (1995) (2)
- Routing and Job-shop Scheduling in O(congestion (1996) (2)
- Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance (2022) (2)
- Representation-Theoretic Techniques for Independence Bounds of Cayley Graphs (2018) (2)
- Information Spread with Error Correction (2021) (2)
- Local decoding and testing of polynomials over grids (2017) (1)
- Streaming complexity of CSPs with randomly ordered constraints (2022) (1)
- The Second Part of the next Claim Follows from a Standard Application of Chernoo Bounds. B General Commodity Testing (1999) (1)
- Compression in a Distributed Setting (2017) (1)
- Deterministic Compression with Uncertain Priors (2016) (1)
- Delays and the Capacity of Continuous-Time Channels (2011) (1)
- Decoding multivariate multiplicity codes on product sets (2020) (1)
- Low-Degree Testing (2015) (1)
- Complexity Theory Column 25 (2007) (1)
- Universal Communication via Robust Coordination (2013) (1)
- A Self-contained Analysis of the Lempel-Ziv Compression Algorithm (2019) (1)
- Special Issue on Randomness and Complexity (2006) (1)
- Effect of Orientation of the Wall Window on Energy Saving under Clear Sky Conditions (2016) (1)
- Quick and Dirty Refereeing? (2003) (1)
- The P vs . NP problem Madhu Sudan (2010) (0)
- Session details: Session 6 (2006) (0)
- Guessing secrets efficiently via list decoding (extended abstract) (2002) (0)
- A ug 2 00 8 Improved lower bound on the size of Kakeya sets over finite fields (2008) (0)
- Towards Universal Semantic Communication ( Version 0-Very Preliminary ) (2007) (0)
- Algebraic algorithms and coding theory (2008) (0)
- Mathematics. Quick and dirty refereeing? (2003) (0)
- Elementary analysis of isolated zeroes of a polynomial system (2021) (0)
- Low-degree tests (1995) (0)
- 7. Classification Theorems for Optimization Problems (2001) (0)
- 5. Implementation of Functions and Reductions (2001) (0)
- Is this correct? Let's check! (2022) (0)
- 8. Input-Restricted Constrained Satisfaction Problems (2001) (0)
- C C ] 2 7 Ju l 2 01 7 Communication with Imperfectly Shared Randomness ∗ (2018) (0)
- Gadgets, Approximation, (Extendied (1996) (0)
- Bounds on 2-Query Codeword (2003) (0)
- General Strong Polarization (2018) (0)
- 9. The Complexity of the Meta-Problems (2001) (0)
- Computational Complexity: a Conceptual Perspective Organization and Chapter Summaries (0)
- Streaming beyond sketching for Maximum Directed Cut (2022) (0)
- Reliable Transmission of Information By Madhu Sudan 1 (2005) (0)
- Linear, Semidefinite Programming and Randomization Methods for Combinatorial Optimization Problems (Dagstuhl Seminar 00041) (2021) (0)
- Advances in Complexity Theory (2004) (0)
- Proof. Reduction from Planar 3-sat. 2 5 Conclusions 4 Translators in General Wdm Networks (1998) (0)
- VII.6 Reliable Transmission of Information (2010) (0)
- Decoding Ag-codes and Let W Be a Vector Having Acknowledgments Decoding Ag-codes (2007) (0)
- 6.s897 Algebra and Computation Lecture 3 (0)
- 2. Complexity Classes (2001) (0)
- Guaranteeing Fair Servi e to Persistent Dependent (2001) (0)
- A Simplified Privacy Preserving Message Delivery Protocol in VDTNs (2018) (0)
- I T ] 8 F eb 2 01 8 General Strong Polarization (2018) (0)
- Lecture 19 - Computing Partial Derivates and Depth Reduction (2012) (0)
- Transitive Transfer of Conndence: a Per- Fect Zero-knowledge Interactive Proto- Col for Sat and Beyond. 5.1 Additional Security for the User (1997) (0)
- Foreword (2022) (0)
- MacWilliams identities (2005) (0)
- Session details: Session 1A (2006) (0)
- On the resilience of polynomials (1995) (0)
- Session details: Session 9 (2006) (0)
- Quasilinear PCPs with Polylog Query Complexity (2006) (0)
- It Follows That M K = N (1997) (0)
- Transparent proofs and the class PCP (1995) (0)
- Physical limits of Communication (Invited Talk) (2011) (0)
- Ideal-theoretic Explanation of Capacity-achieving Decoding (2021) (0)
- Probabilistically Checkable Proofs : A Primer (2006) (0)
- Space-Time Tradeoffs for Graph Properties by Yevgeniy Dodis (0)
- Patterns hidden from simple algorithms (2011) (0)
- Design, Modelling and Optimization of an Electric Vehicle (EV) and Comparison of Performance for Different drive Cycles using MATLAB & SIMULINK (2023) (0)
- 4. Characterizations of Constraint Functions (2001) (0)
- Limits of local algorithms (2013) (0)
- Linearity Testing in Characteristic Two-Information Theory, IEEE Transactions on (2004) (0)
- Bounded Model Checking for the Existential Part of Real-Time CTL and Knowledge (2018) (0)
- 10. Concluding Remarks (2001) (0)
- A Variant of Non-Adaptive Group Testing and Its Application in Pay-Television via Internet (2018) (0)
- Probabilistic Verification of Proofs (1998) (0)
- A Practical Solution against Corrupted Parties and Coercers in Electronic Voting Protocol over the Network (2018) (0)
- Modelling Errors and Recovery for Communication (2006) (0)
- Space-time Tradeoos for Graph Properties Space-time Tradeoos for Graph Properties (1999) (0)
- 2 Overview: Codes From Other Codes (2013) (0)
- Aumann and Rabani On-line Admission Control and Circuit Routing for High Performance Computing and Communication. 4.2 from Throughput to Realization 5 Routing on the Hypercube (0)
- 5.2 Application to Nonapproximability of Optimization Functions (1995) (0)
- 6. Classification Theorems for Decision, Counting and Quantified Problems (2001) (0)
- Dispersers and Extractors for Low-Degree Algebraic Sources (2012) (0)
- News Complexity Theory Column 34 (2010) (0)
- Multicasting layered multimedia streams in an ATM environment (1998) (0)
- Assessment & Evaluation of Anxiety and fear levels towards Dental Treatment- A comparative survey (2022) (0)
- Influence of profession on Gait Pattern and it’s analysis (2020) (0)
- Impact of weather factors on population dynamics of Anosia chrysippus Infesting Calotropis procera, A Medicinal plant in Jammu region of Jammu and Kashmir, India (2015) (0)
- Study on POP Waste & Fibrofor Fiber in Conventional Concrete (2017) (0)
- Complexity of Permutation-Invariant Functions (2015) (0)
- Morphological variations and Ear Biometrics as an aid in identification among populations of Punjab, Haryana and Jammu and Kashmir – A Comparative Study. (2020) (0)
- Performance Parameters Analysis of an XD3P Peugeot Engine Using ANN (2015) (0)
- Henosepilachna vigintioctopunctata (Fabricius) (Coleoptera: Coccinellidae), a serious insect pest of Solanum nigrum (a medicinal plant) in Jammu region (J & K). (2010) (0)
- Sampling system for performance evaluation of friesian crossbred cows (1982) (0)
- BULK MODULUS OF II-VI AND III-V SEMICONDUCTORS (2021) (0)
- A method for induction heat treatment (2011) (0)
This paper list is powered by the following services:
Other Resources About Madhu Sudan
What Schools Are Affiliated With Madhu Sudan?
Madhu Sudan is affiliated with the following schools:
