StarkWare Scholar Summit – Madhu Sudan: The Power of Algebra

In this talk, Madhu Sudan shows how even very basic elements of algebra can yield powerful tools capable of preserving data, expressing logical relations among data, and proving/verifying such relations rapidly.

Specifically, the talk covers using polynomials over finite fields to encode information to protect it from errors. It shows how decoding and list-decoding algorithms can efficiently recover data from noise.

He also shows how polynomials can be used to prove logical statements such as “a given graph G is 3-colorable” so that the proof is easily verifiable.

This style of algebraic thinking lies at the heart of STARKs and the security of some related protocols, such as FRI (although this is not covered in the talk.)

About the speaker:

Madhu Sudan is a Gordon McKay Professor of Computer Science at Harvard University. Madhu Sudan got his Bachelor’s degree from the Indian Institute of Technology at New Delhi in 1987, and Ph.D from the University of California at Berkeley in 1992. Prior to joining Harvard, Madhu Sudan has worked at IBM, MIT, and Microsoft Research.

For his works on Probabilistically Checkable Proofs and List-decoding, Madhu Sudan was awarded the 2002 Nevanlinna Prize, the 2015 Infosys Foundation Prize in Mathematics and the 2022 IEEE Hamming Medal. He is a fellow of the ACM, IEEE, and the AMS, and a member of the National Academy of Sciences. Madhu Sudan’s principal research interests are in reliable communication and computational complexity.

This talk was given at StarkWare Scholar Summit on August 5, 2024. This event brought together a global community of researchers, engineers, and thought leaders to explore the latest and greatest in blockchain tech.