Errors and Correction in Cumulative Knowledge
Societal accumulation of knowledge is a complex, and arguably error-prone, process. The correctness of new units of knowledge depends not only on the correctness of the new reasoning, but also on the correctness of old units that the new one builds on. Left unchecked errors could completely ruin the validity of most of this knowledge – so there must some error-correcting going on. What are the error-corrections processes and how effective are they? In this talk, we present a simple probabilistic process that aims to model such accumulation of knowledge and study the persistence (or lack thereof) of errors.
Our model for the generation of new units of knowledge is based on the preferential attachment growth model, to which we additionally allow for injection of errors. Furthermore, the process includes checks aimed at catching these errors. We investigate when effects of errors persist forever in the system (with positive probability) and when they get rooted out completely by the checking process.
The two basic parameters associated with the checking process are the {\em probability} of conducting a check and the {\em depth} of the check. We show that errors are rooted out if checks are sufficiently frequent and sufficiently deep. In contrast, shallow or infrequent checks are insufficient to root out errors.
Based on the paper: “Is This Correct? Let’s Check!” with Omri Ben-Eliezer, Dan Mikulincer and Elchanan Mossel (all at MIT).
Speaker Biography
Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, where he has been since 2015. Madhu Sudan got his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from U.C. Berkeley in 1992. Between 1992 and 2015, Madhu Sudan worked at IBM Research (Research Staff Member 1992-1997), at MIT (Associate Professor 1997-2000, Professor 2000-2011, Fujitsu Chair Professor 2003-2011, CSAIL Associate Director 2007-2009, Adjunct Professor 2011-2015), and at Microsoft Research (Principal Researcher, 2009-2015). Madhu Sudan is a recipient of the Nevanlinna Prize awarded by the International Mathematical Union for outstanding contributions to mathematics of computer and information science, and the Infosys Foundation Prize in Mathematical Sciences, and the IEEE Hamming Medal. Madhu Sudan is a fellow of the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers and the American Mathematical Society. He is a member of the American Academy of Arts and Sciences and the National Academy of Sciences.
Madhu Sudan’s research interests revolve around mathematical studies of communication and computation. Specifically his research focusses on concepts of reliability and mechanisms that are, or can be, used by computers to interact reliably with each other. His research draws on tools from computational complexity, which studies efficiency of computation, and many areas of mathematics including algebra and probability theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. His current research interests include property testing which is the study of sublinear time algorithms to estimate properties of massive data, and communication amid uncertainty, a mathematical study of the role of context in communication.
