Madhu Sudan: Online talks

This page is under construction (really! perpetually!).

This page contains pdf/powerpoint files corresponding to talks I’ve given. The older powerpoint slides use Tex4ppt. If you don’t wish to install it, then the corresponding pdf files give most of the information (minus some animation).

2024

• Proofs and Computation, Workshop on Milestones and Motifs in the Theory of Proofs, Algebraic Computation, and Lower Bounds. FSTTCS 2024, IIT Gandhinagar, India, December 14, 2024. (abstract, pptx, pdf.)
• Improved PIR Schemes using Matching Vectors and Derivatives, STCS Seminar, Tata Institute of Fundamental Research, Mumbai, India, December 9, 2024. (abstract, pdf.)
• Luca Trevisan: From Contractor to Extractor via Gadgets, “In memory of Luca Trevisan (1971-2024)”, A workshop at Bocconi University, Milan, Italy, December 2, 2024. (abstract, pptx, pdf.)
• Sparsification: Graphs, CSPs and Codes, 7th Eastern Great Lakes (EaGL) Theory of Computation Workshop, University at Buffalo, Buffalo, NY, USA, October 5-6, 2024. (abstract, pptx, pdf.)
• Algebra in Algorithmic Coding Theory, Forward From the Fields Medal, Workshop at the Fields Institute, Toronto, Canada, August 12-17, 2024. (abstract, pdf.)
• The Power of Algebra, StarkWare Scholar Summit, Side event at the Stanford Blockchain Conference, CornellTech campus, NY, NY, USA, August 5, 2024. (abstract, pptx, pdf.)
• Sparsification: Graphs, CSPs and Codes, Workshop on Sublinear Graph Simplification, Simons Institute for the Theory of Computing, Berkeley, CA, USA, July 29-August 2, 2024. (abstract, pptx, pdf.)
• Luca Trevisan: The Early Days, Lucafest: An online collection of videos celebrating the legacy and impact of Luca Trevisan. Released July 21, 2024. (slides (pptx), slides (pdf) Youtube video link.)
• Universality in Communication, Workshop on “Computing on the dark side: Celebrating Leonid Levin’s work”. Boston University, Boston, MA, USA, July 10-11, 2024. (abstract, pptx, pdf.)
• Local Correction of Linear Functions over the Boolean Cube, STCS Seminar, Tata Institute of Fundamental Research, Mumbai, India, May 28, 2024. (abstract, pptx, pdf.)
• Errors and Correction in Cumulative Knowledge, CMSA Colloquium, Harvard University, Cambridge, MA, May 13, 2024. (abstract, pptx, pdf.)
• Mathematical Theories of Communication: Old and New, CRM Colloquium, 40th Anniversary Celebration of the Centre de Recerca Matemática, Barcelona, May 9, 2024. (abstract, pptx, pdf.)
• Modern Highlights of Algorithmic Coding Theory, 3 lecture mini-course taught at U. Barcelona under the auspices of the CRM, Barcelona, May 6-8, 2024. (abstract, website with lecture notes.)
• Sparsification: Graphs, CSPs and Codes, CSDM Seminar, Institute for Advanced Study, Princeton, NJ, USA April 15, 2024. (abstract, pptx, pdf.)

2023

• Jaikumar and the Entropy Method in Combinatorics, STCS Farewell Workshop honoring Jaikumar Radhakrishnan, Tata Institute of Fundamental Research, Mumbai, India, December 14, 2023. (pptx, pdf.)
• Sparsification: Graphs, CSPs and Codes, STCS Seminar, Tata Institute of Fundamental Research, Mumbai, India, December 11, 2023. (abstract, pptx, pdf.)
• Proofs and Computation, Harvard Math Picture Language Seminar, Harvard University, Cambridge, MA, USA, October 3, 2023. (abstract, pptx, pdf.)
• Approximately 50 years of inapproximability, Workshop celebrating 70 years of Mihalis Yannakakis, Columbia University, New York, NY, USA, August 16-18, 2023. (abstract, pptx, pdf.)
• Low Degree Testing, Keynote Lecture, Workshop on Algebra and Computation, Göteborg, Sweden, August 14-16, 2023. (abstract, pptx, pdf.)
• Errors and Correction in Cumulative Knowledge, CS Seminar, Indian Institute of Technology Bombay, Mumbai, India, March 16, 2023. (abstract, pptx, pdf.)
• Errors and Correction in Cumulative Knowledge, STCS Seminar, Tata Institute of Fundamental Research, Mumbai, India, March 13, 2023. (abstract, pptx, pdf.)

2022

• Streaming Complexity of Constraint Satisfaction Problems, MIT FODSI Sublinear Algorithms Workshop, MIT, Cambridge, MA, USA, August 3-5, 2022. (abstract, pptx, pdf.)
• Streaming Complexity of Constraint Satisfaction Problems, BIRS Workshop on Communication Complexity and Applications III, Banff International Research Center, Banff, Alberta, Canada, July 24-29, 2022. (abstract, pptx, pdf.)
• Streaming and Sketching Complexity of CSPs: A Survey, Invited Speaker, ICALP 2022, Paris, France, July 4-8, 2022. (pptx, pdf.)
• Survey of Polar Codes, STOC22/TheoryFest Workshop on Recent Advances in Algorithmic Coding Theory, Rome, Italy, June 22-24, 2022. (abstract, pptx, pdf.)
• Streaming Complexity of Constraint Satisfaction Problems, CS Colloquium, Tata Institute of Fundamental Research, Mumbai, India, April 8, 2022. (abstract, pptx, pdf.)
• Streaming Complexity of Constraint Satisfaction Problems, CS Theory Seminar, Indian Institute of Technology at Bombay, Mumbai, India, April 4, 2022. (abstract, pptx, pdf.)
• Universal Semantic Communication, CETI Seminar/Discussion Series, Virtual event, March 8, 2022. (abstract, pptx, pdf.)

2021

• A Picture is Worth a Thousand Words, Its Essence is Checked in Three, (Virtual talk), CS Colloquium, Indian Institute of Technology at Delhi, December 6, 2021. (abstract, pdf.)
• A brief self-introduction, (Virtual talk), CS Lunch, Harvard, September 16, 2021. (pptx, pdf.)
• Streaming Complexity of Constraint Satisfaction Problems, (Virtual talk), Workshop on Algorithms for Large Data (Online) – WALDO 2021, August 23-25, 2021. (abstract, pptx pdf.)
• A Picture is Worth a Thousand Words, Its Essence is Checked in Three, Stark@Home (informal webinar on topics related to STARK), June 23, 2021. (abstract, pdf, link to video.)
• Highlights of Algorithmic Coding Theory, School in Algorithms, Combinatorics, and Complexity hosted by St. Petersburg University, May 24-28, 2021. (abstract, website with lecture notes and links to videos.)
• (Deterministic) Communication Amid Uncertainty, Budapest Big Seminar on Combinatorics and Geometry, April 2, 2021. (abstract, pdf, video.)

2020

• Communication Amid Uncertainty, First IBM Research Workshop on the Informational Lens, (a virtual event), September 29-October 1, 2020. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, CS Colloquium, (held virtually), Georgetown University, Washington D.C., USA, September 17, 2020. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Spotlight talk, Workshop on Local Algorithms (WOLA 2020). Held virtually – see https://www.mit.edu/~mahabadi/workshops/WOLA-2020.html (abstract, pdf.)
• Coding for Editing Errors, Arbeitsgemeinschaft in Codierungstheorie und Kryptographie, Mathematics Institute, University of Zurich, May 6, 2020. (abstract, pdf.)
• Polarization of Bounded Martingales, Applied Mathematics Colloquium, Brown University, January 28, 2020. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Theory Lunch, Computer Science Department, Princeton University, January 10, 2020. (abstract, Powerpoint, pdf.)

2019

• Data Compression: A Survey, Theory Seminar, CS Department, IIT Bombay, Mumbai, India, December 19, 2019. (abstract, Powerpoint, pdf.)
• Proofs and Computation, Renaissance Colloquium, Renaissance Technologies, East Setauket, NY, USA, December 10, 2019. (abstract, Powerpoint, pdf.)
• Limits of Local Algorithms on Sparse Random Graphs, Optimization Seminar, ORFE Dept, Princeton University, Princeton, NJ, USA, December 5, 2019. (abstract, Powerpoint, pdf.)
• Communication Complexity of Randomness Manipulation, CMSA Colloquium, Harvard Universeity, Cambridge, MA, USA, November 25, 2019. (abstract, Powerpoint, pdf.)
• Context in Communication, FOCS 2019 Tribute to Shafi Goldwasser, Baltimore, USA, November 9, 2019. (Powerpoint, pdf.)
• Communication Amid Uncertainty, IC Colloquium, EPFL, Lausanne, October 31, 2019. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Algo UK, University of Warwick, Coventry, England, September 17-18, 2019. (abstract, Powerpoint, pdf.)
• Information Theory in CS, Swedish Summer School in Computer Science, S3CS 2019, (Mini-course, 15 lectures x 45 minutes), KTH Stockholm. July 1–5, 2019.
• Communication Complexity of Randomness Manipulation, Mathematics Seminar, Indian Institute of Technology Bombay, Mumbai, India. May 29, 2019. (abstract, Powerpoint, pdf.)
• Communication Complexity of Randomness Manipulation, CS Seminar, Tata Institute of Fundamental Research, Mumbai, India. May 29, 2019. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Workshop on Contemporary Coding Theory, MFO, Oberwolfach, Germany. March 20, 2019. (abstract, Powerpoint, pdf.)
• On the resilience of polynomials, IBM Research Seminar, IBM Research, Cambridge, MA, USA, April 29, 2019. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Workshop on Contemporary Coding Theory, MFO, Oberwolfach, Germany. March 20, 2019. (abstract, Powerpoint, pdf.)
• What should I talk about?, CINCS Seminar Series, a series on Communication, Information, Networking, Circuits and Signal Processing, MIT, Cambridge, MA, USA, February 13, 2019. (abstract, Powerpoint, pdf.)
• Speaking of Proofs, Shafifest, A celebration of Shafi Goldwasser, Berkeley, CA, USA, January 13, 2019. (abstract, Powerpoint, pdf.)
• General Strong Polarization, ACO Seminar Series, University of California at Irvine, CA, USA. January 10, 2019. (abstract, Powerpoint, pdf.)

2018

• Communication Complexity of Randomness Manipulation, Lower Bounds Seminar, Simons Institute for the Theory of Computing, Berkeley, CA, USA, October 31, 2018. (abstract, Powerpoint, pdf.)
• Mathematical Theories of Communication: Old and New, Open Lecture, Simons Institute for the Theory of Computing, Berkeley, CA, USA, October 22, 2018. (abstract, Powerpoint, pdf.)
• General Strong Polarization, CS Theory Seminar, U.C. Berkeley, CA, USA, October 8, 2018. (abstract, Powerpoint, pdf.)
• General Strong Polarization, CS Theory Seminar, Stanford Univerity, Stanford, CA, USA, October 5, 2018. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Theory Seminar, Google Research, Mountainview, CA, USA, September 4, 2018. (abstract, Powerpoint, pdf.)
• Edit Distance Error-Correction and Synchronization Strings, SCS Colloquium, Tata Institute of Fundamental Research, Mumbai, India, July 11, 2018. (Board talk, so no slides, but here is the abstract, and some notes.)
• General Strong Polarization, CS Theory Seminar, Cornell University, Ithaca, NY, USA, May 1, 2018. (abstract, Powerpoint, pdf.)
• General Strong Polarization, ARC Colloquium, Georgia Institute of Technology, Atlanta, GA, USA, May 18, 2018. (abstract, Powerpoint, pdf.)
• General Strong Polarization, DIMACS Theory of Computing Seminar, Rutgers University, New Brunswick, NJ, USA, April 4, 2018. (abstract, Powerpoint, pdf.)
• Local decoding and testing of polynomials over grids, ITCS 2018 , Conference Presentation, MIT, Cambridge, MA, USA, January 11, 2018. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, ICTS at Ten, Symposium to celebrate the tenth anniversary of the International Centre for Theoretical Sciences, Bengaluru, India, January 5, 2018. (abstract, Powerpoint, pdf.)

2017

• General Strong Polarization, CS/Discrete Math Seminar, Institute for Advance Study, Princeton, NJ, USA, December 4, 2017. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Probability Group Meeting, Harvard University, Cambridge, MA, USA, October 23, 2017. (Whiteboard talk. No slides.) abstract.)
• Mathematical Theories of Communication: Old and New, Heidelberg Laureates Forum, Heidelberg, Germany. September 26, 2017. (abstract, Powerpoint, pdf.)
• General Strong Polarization, Harvard/MIT/MSR Theory Reading Group, Harvard University, Cambridge, MA, USA, September 15, 2017. (Talk given jointly with Jaroslaw Blasiok and Preetum Nakkiran. No slides. abstract.)
• Communication Amid Uncertainty, Workshop on Proof Complexity and Beyond, Mathematische Forschungsinstitut Oberwolfach, Oberwolfach, Germany. August 14-18, 2017. (abstract, Powerpoint, pdf.)
• General Strong Polarization, CS Colloquium, Indian Institute of Technology Bombay, Mumbai, India. August 11, 2017. (abstract, Powerpoint, pdf.)
• General Strong Polarization, CS Colloquium, Tata Institute of Fundamental Research, Mumbai, India. August 09, 2017. (abstract, Powerpoint, pdf.)
• Uncertain Compression and Graph Coloring, Mathematics Colloquium, Indian Institute of Technology Bombay, Mumbai, India. August 04, 2017. (abstract, Powerpoint, pdf.)
• What should I talk about?, Randomness, Complexity, and Cryptography: The first sixty years of Oded Goldreich, Weizmann Institute of Science, Rehovot, Israel. April 20, 2017. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Distinguished Lecture, Computer Science department, University of California at Riverside, CA, USA, February 24, 2017. (abstract, Powerpoint, pdf.)
• Mathematics, Proofs and Computation, N. R. Kamath Chair Lecture, Indian Instiute of Technology Bombay, Mumbai, India, January 4, 2017. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Workshop on Mathematics and Information, Department of Mathematics, Indian Instiute of Technology Bombay, Mumbai, India, January 2, 2017. (abstract, Powerpoint, pdf.)

2016

• The Polynomial Method and Variations, Mathematics Colloquium, Indian Institute of Technology Bombay, Mumbai, India, December 28, 2016. (abstract, pdf of crude handwritten notes, one-note source if the line breaks in pdf make it impossible to read.)
• Mathematics, Proofs and Computation, Plenary Lecture, TIMC-AMS Joint Conference, Banaras Hindu University, Varanasi, India, December 16, 2016. (abstract, Powerpoint, pdf.)
• Non-Interactive Simulation, Session on Mathematics of Computer Science, TIMC-AMS Joint Conference, Banaras Hindu University, Varanasi, India, December 15, 2016. (pdf.)
• Communication with Imperfectly Shared Randomness, Mathematics Colloquium, University of Toronto, Ontario, Canada, November 16, 2016. (abstract, Powerpoint, pdf.)
• Locality in Coding Theory, Workshop on Local Algorithms, Microsoft Research and MIT, Cambridge, MA, USA. October 14-15, 2016. (abstract, Powerpoint, pdf.)
• Low Degree Polynomials, Avi is 60: A celebration of Mathematics and Computer Science, Institute for Advanced Study, Princeton, NJ, USA. October 7, 2016. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Theory of Computing Colloquium, MIT, Cambridge, MA, USA. May 10, 2016. (abstract, Powerpoint, pdf.)
• Algebraic Codes and Invariance, Invited lecture, Applied Algebra Days 3, University of Wisconsin, Madison, WI, USA. April 29 – May 1, 2016. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Keynote lecture, Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics, Moscow, Russia. April 9-13, 2016. (abstract, Powerpoint, pdf.)
• Locality in Coding Theory (in two parts – Part I, Part II), Tutorials Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics, Moscow, Russia. April 9-13, 2016. (abstract, Part I (pdf), Part II (pdf)).
• Two decades of Property Testing, Workshop on Theoretical Computer Science, Higher school of Economics, Moscow, Russia, April 6-8, 2016. (abstract, Powerpoint, pdf.)
• Mathematics, Proofs and Computation, Public Lecture Center for Excellence in Basic Sciences, Mumbai, India, January 7, 2016. (Part of the IASc Jubilee Professor Lecture Series.) (abstract, Powerpoint, pdf.)
• Reliable Meaningful Communication, Public Lecture Indian Institute of Science Education and Research, Pune, India January 5, 2016. (Part of the IASc Jubilee Professor Lecture Series.) (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, Bombay Information Theory Symposium (BITS 2016), IIT Bombay and Tata Institute of Fundamental Research, Mumbai, India, January 3, 2016. (abstract, Powerpoint, pdf.)

2015

• Property Testing and Affine Invariance (in two parts – Part I, Part II), Mathematics Seminar IIT Bombay, Mumbai, India, 29-30 December 2015. (Part of the IASc Jubilee Professor Lecture Series.) (abstract, Part I (pdf), Part II (pdf)).
• Laws of Communication of Thought, Boole Shannon Lecture Series, MIT, Cambridge, MA, USA, December 3, 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, CS Distinguished Lecture, Washington University at St. Louis, October 30, 2015. (abstract, Powerpoint, pdf.)
• Communication Amid Uncertainty, CS Distinguished Lecture, University of Massachusetts, Amherst, October 7, 2015. (abstract, Powerpoint, pdf.)
• 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.)
• Reliable Meaningful Communication, EE Seminar, KAIST, Daejeon, Korea, 6 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.)