Madhu Sudan: Online talks

2015

• Robust low-degree testing, CMSA Colloquium, Center for Mathematical Sciences and Applications, Harvard, 2 September 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Theory of Computation Seminar, Harvard University, 31 August 2015. (abstract, Powerpoint, pdf.)
• Algebraic Codes and Invariance, Plenary Lecture, SIAM Conference on Applied Algebraic Geometry, 4 August 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Theory seminar, Computer Science Dept., Carnegie-Mellon University, 28 July 2015. (abstract, Powerpoint, pdf.)
• Locality in Coding Theory, Plenary Lecture, IEEE International Symposium on Information Theory, Hong Kong, 16 June 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, CS Theory Seminar, Chinese University of Hong Kong, Hong Kong, 15 June 2015. (abstract, Powerpoint, pdf.)
• Probabilistically Checkable Proofs, Infosys Science Foundation Lecture Series, Tata Institute of Fundamental Research, Mumbai, India, 11 June 2015. (abstract, Powerpoint, pdf.)
• Reliable Meaningful Communication, Infosys Science Foundation Lecture Series, IIT Bombay, Mumbai, India, 8 June 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Theory Seminar, Toyota Technological Institute, Chicago, Illinois, USA, 21 May 2015. (abstract, Board talk, so no slides. Somewhat based on this older talk.)
• Low-Degree Testing, Mathematics Colloquium, U. Chicago, Chicago, Illinois, USA, 20 May 2015. (abstract, Powerpoint, pdf).
• Imperfectly Shared Randomness in Communication, MSR Theory Day, Microsoft Research, Redmond, WA, USA, 26 March 2015. (abstract, Powerpoint, pdf).
• Locality in Codes and Lifting, CS Theory Seminar, University of Washington, Seattle, WA, USA, 24 March 2015. (abstract, Powerpoint, pdf).
• Imperfectly Shared Randomness in Communication, TCS+ seminar, presented online, 4 March 2015. (abstract, Powerpoint, pdf).
• Locality in Codes and Lifting, ECE Seminar, Indian Institute of Sciences, Bengaluru, India, 19 January 2015. (abstract, Powerpoint, pdf).
• Low Degree Testing, Mathematics Seminar, Indian Institute of Technology Bombay, Mumbai, India. 14 January 2015. (abstract, Board talk, so no slides. Based on this older talk.)
• Imperfectly Shared Randomness in Communication, CS Seminar, Tata Institute of Fundamental Research, Mumbai, India, 12 January 2015. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, Silver Jubilee Lectures, Chennai Mathematics Institute, Chennai, India, 6 January 2015. (abstract, Powerpoint, pdf).
• Reliable Meaningful Communication, Indian Science Congress, Session on Recent Advances in Mathematics and Computing, University of Mumbai, Mumbai, India, 3 January 2015. (abstract, Powerpoint, pdf).

2014

• Two Decades of Property Testing, Theory of Computing Colloquium, MIT, Cambridge, MA, USA, 10 November 2014. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, CS Colloquium, Harvard University, Cambridge, MA, USA, 10 November 2014. (abstract, Powerpoint, pdf).
• Communication with Imperfectly Shared Randomness, Probability Seminar, MIT, 3 November, 2014. (abstract, Powerpoint, pdf).
• Communication with Imperfectly Shared Randomness, Theory Seminar, Microsoft Research India, Bengaluru, India, 8 October, 2014. (abstract, Powerpoint, pdf).
• Limits of Local Algorithms on Sparse Random Graphs, Mathematics Seminar, Indian Institute of Technology, Mumbai, India, 7 October, 2014. (abstract, Powerpoint, pdf).
• Limits of Local Algorithms on Sparse Random Graphs, CS Seminar, Tata Institute of Fundamental Research, Mumbai, India, 4 October, 2014. (abstract, Powerpoint, pdf).
• Coding for Interactive Communication: A survey of recent progress, CS Seminar, Tata Institute of Fundamental Research, Mumbai, India, 4 October, 2014. (abstract, pdf - Warning: Raw Notes!!).
• Polynomial Method and Variations, Undergraduate Math Association, MIT, 15 April 2014. (abstract, pdf).
• Reliable Meaningful Communication, I.G. Sarma Memorial Lecture, Indian Institute of Sciences, Bengaluru, India, 22 January 2014. (abstract, Powerpoint, pdf).

2013

• Communication as Coordination, CSOI-NSF Site Visit Workshop, Center for Science of Information, Purdue University, West Lafayette, IN, USA. 4 December 2013. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, Samuel Conte Distinguished Lecture, CS Department, Purdue University, West Lafayette, IN, USA. 2 December 2013. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, CS Colloquium, Cornell University, Ithaca, NY, USA, 31 October 2013. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, Microsoft Research New England 5th Anniversary Celebration, Cambridge, MA, USA. 8 October 2013. (Powerpoint, pdf).
• Communication Amid Uncertainty, Lunch Seminar, MIT Laboratory for Information and Decision Systems, Cambridge, MA, USA. 1 October 2013. (Powerpoint, pdf).
• Reliable Meaningful Communication, 1st Heidelberg Laureates Forum, Heidelberg, Germany, 24 September 2013. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, CS Colloquium, Cornell University, Ithaca, NY, USA, 31 October 2013. (abstract, Powerpoint, pdf).
• Invariance in Property Testing (in two parts - Part I, Part II), Mysore Park Workshop on Recent Trends in Algorithms and Complexity, Infosys Mysore Campus, Mysore, India, 16 August 2013. (abstract, Part I, Part II).
• Limits of local algorithms over sparse random graphs, Workshop on Computational Complexity, Banff International Research Station, Banff, Alberta, Canada 11 July 2013. (abstract, Powerpoint, pdf).
• Locality in Codes and Lifting, Mathematics of Information Theoretic Cryptography, Lorentz Center, Leiden, The Netherlands. 24 May 2013. (abstract, Powerpoint, pdf).
• New locally decodable codes from lifting, CS Seminar, Institute for Advanced Study, Princeton, USA. 25 March 2013. (abstract, Powerpoint, pdf).
• Communication and Computing, Microsoft Research, Redmond, USA. 7 March 2013. (abstract, Powerpoint, pdf).

2012

• Deterministic Communication Amid Uncertainty, CS Seminar, Microsoft Research India, Bangalore, India. 26 November 2012. (abstract, Powerpoint, pdf).
• Deterministic Communication Amid Uncertainty, CS Seminar, Tata Institute of Fundamental Research, Mumbai, India. 20 November 2012. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, EECS Distinguished Lecture, Northwestern University, Chicago, IL, USA. 17 October 2012. (abstract, Powerpoint, pdf).
• Communication Amid Uncertainty, Plenary talk, Information Theory Workshop (ITW 2012), EPFL, Lausanne, Switzerland. 4 September 2012. (abstract, Powerpoint, pdf).
• Communication amid Uncertainty, CSOI workshop at ISIT, MIT, Cambridge, MA, USA. 1 July 2012. (Powerpoint, pdf).
• Communication amid Uncertainty, CSOI Student workshop, Stanford University, Stanford, CA, USA. 30 May 2012. (Powerpoint, pdf).
• Communication amid Uncertainty, Communication Theory Workshop (CTW 2012), Maui, Hawaii, USA. 16 May 2012. (Powerpoint, pdf).
• Compression under Uncertain Priors, 46th Annual Conference on Information Science and Systems, Session on Goal-Oriented Communication, Princeton University, Princeton, New Jersey, USA. 22 March 2012. (Powerpoint, pdf).
• Efficient Semantic Communication via Compatible Beliefs, 46th Annual Conference on Information Science and Systems, Session on Science of Information: New Perspectives, Princeton University, Princeton, New Jersey, USA. 21 March 2012. (Powerpoint, pdf).
• Invariance in Property Testing, Colloquium, Department of Mathematics, Yale University, New Haven, Connecticut, USA. 22 February 2012. (Abstract, Powerpoint, pdf).
• Invariance in Property Testing, Short presentation, Simons Foundation Workshop on Analysis of Boolean functions, St. Johns, US Virgin Islands, USA(?), 6-10 February 2012. (pdf).

2011

• Multiplicity Codes: Locality with High Efficiency, Workshop on Breakthroughs in Theoretical Computer Science, Computer Science Department, Indian Institute of Technology, Mumbai, India. 16 December 2011. (Abstract, Powerpoint, pdf).
• Physical Limits of Communication, Invited Lecture, Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Indian Institute of Technology, Mumbai, India, 12-14 Demeber 2011. (Abstract, Powerpoint, pdf).
• Invariance in Property Testing, Theory Seminar, Computer Science Department, University of Chicago, Chicago, Illinois, USA. 18 October 2011. (Abstract, Powerpoint, pdf).
• Communication, Computing and Technology, Short talk, MSR 20th Anniversary Celebration, Microsoft Research New England, Cambridge, MA, USA, 27 September 2011. (Abstract, Powerpoint, pdf).
• Communication versus Computing, Distinguished Lecture, Computer Science Department, University of Illinois at Urbana-Chapmpaign, Illinois, 19 September 2011. (Abstract, Powerpoint, pdf).
• Invariance in Property Testing, Michael Rabin Celebration, Conference in celebration of Michael Rabin's 80th birthday at Harvard University, 29-30 August 2011. (Abstract, Powerpoint, pdf).
• Testing Affine-Invariant Properties, Workshop on Combinatorial, Algebraic and Algorithmic Aspects of Coding Theory, Centre Interfacultaire Bernoulli, EPF Lausanne, 25-29 July 2011. (Abstract, Powerpoint, pdf).
• Local Algorithms & Error-Correction, , IPPI 50th Anniversary Mathematical Conference, Russian Academy of Sciences, Moscow, 25-29 July 2011. (Abstract, Powerpoint, pdf).
• The Method of Multiplicities, International Computer Science Symposium in Russia (CSR 2011), Academic University, St. Petersburg, Russia, 13-18 June 2011. (Abstract, Powerpoint, pdf).
• Testing Affine-Invariant Properties, Workshop on Sublinear Algorithms, Bertinoro international Center for informatics (BiCi), Bertinoro, 23-27 March 2011. (Abstract, Powerpoint, pdf).
• Towards Universal Semantic Communication, Theory Seminar, EECS Department, Northwestern University, May 2, 2011. (Abstract, Powerpoint, pdf).
• Local List Decoding, Workshop on Mathematics of Information-Theoretic Cryptography, Institute for Pure and Applied Mathematics, University of California at Los Angeles, March 2, 2011. (Abstract, Powerpoint, pdf).
• Semantic Goal-Oriented Communication, Jon Postel Distinguished Lecturer Series, CS Department, University of California at Los Angeles, March 1, 2011. (Abstract, Powerpoint, pdf).

2010

• Probabilistically Checkable Proofs, Guest Lecture in course on Topics in Algorithms taught by Sanjeev Khanna, CS Department, University of Pennsylvania, October 20, 2010.
• Semantic Goal-Oriented Communication, CS Distinguished Lecture, University of Pennsylvania, October 19, 2010. (Abstract, Powerpoint, pdf).
• Semantic Goal-Oriented Communication, CS Distinguished Lecture, University of Waterloo, October 14, 2010. (Abstract, Powerpoint, pdf).
• Computing and Communication, Kickoff Meeting of NSF's Science and Technology Center on the Emerging Frontiers of the Science of Information, October 6, 2010. (Abstract, Powerpoint, Pdf).
• The Method of Multiplicities, Stanford Theory Seminar, September 24, 2010. (Abstract, Powerpoint, Pdf).
• Semantic Goal-Oriented Communication, EECS Colloquium Distinguished Lecture, University of California at Berkeley, September 23, 2010. (Abstract, Powerpoint, pdf).
• Invariance in Property Testing, Theory Seminar, Microsoft Research, Silicon Valley Center, Mountainview, California, September 20, 2010. (Abstract, Powerpoint, pdf).
• The Method of Multiplicities, SIAM Discrete Math Conference, Austin, Texas, USA June 16, 2010. (Abstract, Powerpoint, Pdf, Link to webcast).
• The Method of Multiplicities, Theory Seminar Microsoft Research, Bangalore, India, May 5, 2010. (Abstract, Powerpoint, pdf).
• Invariance in Property Testing, Combinatorics, Groups, Algorithms, and Complexity, Conference in honor of Laci Babai's 60th Birthday, The Ohio State University, Columbus, Ohio, March 20-25, 2010. (Abstract, Powerpoint, pdf).
• Semantic Goal-Oriented Communication, Ericsson CWC Communications and Networking Seminar, University of California at San Diego, March 1, 2010. (Abstract, Powerpoint, pdf).
• The Method of Multiplicities, CS Theory Seminar Carnegie-Mellon University, February 19, 2010. (Abstract, Powerpoint, pdf).
• Error-correcting Codes: Recent Progress and Challenges, Guest Lecture in course on Coding Theory taught by Venkatesan Guruswami, Carnegie-Mellon University, February 19, 2010. (Powerpoint, pdf).
• Semantic Goal-Oriented Communication, Computational Thinking Seminar, School of Computer Science, Carnegie-Mellon University, February 18, 2010. (Abstract, Powerpoint, pdf).
• Semantic Goal-Oriented Communication, TOC Colloquium, CSAIL, MIT, Cambridge, MA, USA, February 2, 2010. (Powerpoint, pdf).
• Invariance in Property Testing, Workshop on Property Testing, Institute for Theoretical Computer Science, Tsinghua University, Beijing, China, January 8 - 10, 2010. (Powerpoint, pdf).

2009

• Invariance in Property Testing, Workshop on Analytical Methods in Combinatorics, Additive Number Theory and Computer Science. Institute for Pure and Applied Mathematics, UCLA, Los Angeles, CA, USA, December 1 - 4, 2009. (Powerpoint, pdf).
• Universal Semantic Communication, Informal presentation, Oberwolfach meeting on Complexity Theory, November 15-21, 2009. (Powerpoint, pdf).
• Universal Semantic Communication, Computer Science Colloquium Series, Harvard University, Cambridge, MA, USA, October 1, 2009. (Powerpoint, pdf).
• Probabilistically checkable proofs, MIT Logic Colloquium, Cambridge, MA, USA, September 23, 2009. (pptx).
• Semantic Communication, (Cheat-slides for a whiteboard presentation) at lunch at Microsoft Research, MSR New England, Cambridge, MA, USA, August 6, 2009. (pptx).
• Invariance in Property Testing, Microsoft Research Seminar, MSR New England, Cambridge, MA, USA, June 10, 2009. (pdf).
• Invariance in Property Testing, Theory Seminar, CS Department, University of Texas at Austin, Austin, Texas, USA, May 1, 2009. (ppt, pdf).
• Probabilistically Checkable Proofs, Second Lecture, Maxson Lecture Series, Texas A&M University, College Station, Texas, USA, April 30, 2009. (ppt, pdf).
• List-Decoding of Reed-Solomon Codes, First Lecture, Maxson Lecture Series, Dept. of Mathematics, Texas A&M University, College Station, Texas, USa April 29, 2009.
• Communication and Computation: A need for a unifying theory?, CS Distinguished Lecture University of Texas at Austin, Austin, Texas, USA, April 28, 2009. (ppt, pdf).
• Algebraic Property Testing: A Survey, Workshop on Property Testing DIMACS, Rutgers University, New Jersey, USA, April 1, 2009. (ppt, pdf).
• (Computational) Complexity in Everyday Life, Public Lecture in the series Love in the time of the internet hosted by the University of Rome, La Sapienza, and the Goethe Institute, Rome, Italy, March 24, 2009. (ppt, pdf).
• Universal Semantic Communication, CS Seminar, University of Rome, La Sapienza, Rome, Italy, March 23, 2009. (ppt, pdf).
• Local Algorithms and Error-Correction, Keynote Lecture, Workshop on Information Theory and Applications (ITA 2009), San Diego, CA, USA, February 11, 2009. (ppt, pdf).

2008

• Communicating Computers and Computing Communicators: A need for a new unifying theory, Department Distinguished Seminar, CS Department, University of Rochester, Rochester, NY, USA, November 17, 2008. (ppt, pdf).
• Communicating Computers and Computing Communicators: A need for a new unifying theory, Triangle Computer Science Distinguished Lecturer Series, University of North Carolina, Chapel Hill, NC, USA, November 3, 2008. (ppt, pdf; video available from here).
• Universal Semantic Communication, Research Spotlight, MIT CSAIL Lunch Series, MIT, Cambridge, USA, October 30, 2008. (ppt).
• Research in Theoretical Computer Science, MIT-Foxconn Workshop, Taipei, Taiwan, October 27, 2008. (ppt).
• Towards Universal Semantic Communication, First China Symposium on Theoretical Computer Science, ITCS, Tsinghua University, Beijing, Canada, October 14, 2008. (ppt, pdf).
• Local Testability and Decodability of Sparse Linear Codes, Seminar, Institute for Theoretical Computer Science, Tsinghua University, Beijing, China, October 10, 2008. (ppt, pdf).
• Local Testability and Decodability of Sparse Linear Codes, CS Theory Seminar, Tata Institute of Fundamental Research, Mumbai, India, October 6, 2008. (ppt, pdf).
• Towards Universal Semantic Communication, BIRS Workshop on Analytic Tools in Computational Complexity, Banff, Alberta, Canada, August 5, 2008. (ppt, pdf).
• Algebraic Algorithmic and Coding Theory, Tutorial lecture, ISSAC 2008, Hagenberg, Austria, July 20, 2008.
• Universal Semantic Communication, Distinguished Lecture Series, CS Department, SUNY Buffalo, Buffalo, New York, USA, April 17, 2008. (ppt, pdf).
• 2-Transitivity is insufficient for property testing, Student seminar, Weizmann Institute of Sciences, Rehovot, Israel, March 31, 2008.
• Local Testability and Decodability of Sparse Linear Codes, Theory Seminar, Weizmann Institute of Sciences, Rehovot, Israel, March 31, 2008 (ppt, pdf).
• Universal Semantic Communication, CS Colloquium, Technion, Haifa, Israel, March 25, 2008. (ppt, pdf).
• The Role of Invariance in Property Testing, Colloquium, Microsoft Research India, Bangalore, India, January 8, 2008. (ppt, pdf).
• Universal Semantic Communication, Colloquium, Tata Research, Development and Design Center, Pune, India, January 4, 2008. (ppt, pdf).
• Universal Semantic Communication, CS Colloquium, IIT Mumbai, Mumbai, India, January 3, 2008. (ppt, pdf).

2007

• Local Error-Detection and Error-Correction, Plenary Lecture, AAECC 2007, Bangalore, India, December 17, 2007. (ppt, pdf).
• Algebraic Property Testing, Mathematics Colloquium, U. Frankfurt, Frankfurt, Germany, June 22, 2007. (ppt, pdf).
• Algebraic Property Testing, CS Colloquium, Tata Institute of Fundamental Research, Mumbai, India, December 31, 2007. (ppt, pdf).
• Universal Semantic Communication, Theory Day at Microsoft Research India, Bangalore, India, December 22, 2007. (ppt, pdf).
• Universal Semantic Communication, Short report, Oberwolfach workshop on Computational Complexity, Mathematical Research Institute, Oberwolfach, Germany, June 29, 2007. (ppt, pdf).
• Universal Semantic Communication, Theory Seminar, Institute for Advanced Study, Princeton, New Jersey, USA, September 24, 2007. (ppt, pdf).
• Towards Universal Semantic Communication, TOC Colloquium, MIT, Cambridge, Massachusetts, USA, February 13, 2007. (ppt, pdf).
• Universal Semantic Communication, Prestige Lecture Series, Purdue University, West Lafayette, Indiana, USA, April 16, 2007. (ppt, pdf).
• Universal Semantic Communication, CS Colloquium, Warsaw University, Warsaw, Poland, October 4, 2007. (ppt, pdf).
• Universal Semantic Communication, Theory Colloquium, Weizmann Institute of Sciences, Rehovot, Israel, May 27, 2007. (ppt, pdf).
• List Decoding: Background and Recent Advances, AAECC-17, Bangalore, India, December 18, 2007
• Alberta List
• AofA
• PTMAMS-List
• RSA-List
• U. Wisc. DL, List-decoding stuff?, 11/15/2006
• Universal Semantic Communication", CS Seminar, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, January 16, 2007.
• Universal Semantic Communication", MIT TOC Colloquium, February 13, 2007.
• Universal Semantic Communication", Algorithms and Randomness Center (ARC) Colloquium, Georgia Institute of Technology, February 19, 2007.
• List decoding: Survey of recent results", Seminar, Claude Shannon Institute, University College Dublin, Ireland, March 22, 2007.

2006

• Algebraic Property Testing, Theory Seminar, U. Wisconsin, Madison, Wisconsin, USA, November 16, 2006.
• Probabilistic Checking of Proofs, Current Events Session, Joint AMS-MAA Meeting,, San Antonio, Texas, January 14, 2006. December 17, 2007. (ppt, pdf).

Prehistoric

Some ancient talks in random order.

Error Correcting Codes: Progress and Challenges: (A survey-ish talk presented at MSR Redmond and IAS, 2005).

Coding Theory: Tutorial/Survey. (Slides of a two hour tutorial on coding theory. The accompanying paper is here. )

Probabilistic checking of proofs. (Four hours of lectures on PCP, from talks given a graduate summer school organized by the Park City Mathematical Institute at the Institute for Advanced Study, Princeton, NJ, July 15 - August 5, 2000.)

PCP and Inapproximability: Survey and Open Problems. (Talk given at DIMACS workshop on Approximability of NP-hard problems, Nassau Inn, Princeton, NJ, 20-22 February 2000.)

List decoding of polynomial codes. (Covers joint works with Sanjeev Arora, Venkatesan Guruswami, Luca Trevisan and Salil Vadhan.)

Hardness of approximating the minimum distance of a linear code. (Joint work with Ilya Dumer and Daniele Micciancio.)

Chinese remaindering with errors. (Joint work with Oded Goldreich and Dana Ron.)

Linear consistency testing. (Joint work with Yonatan Aumann, Johan Hastad, and Michael O. Rabin.)