Section 14. Mathematics of Computer Science

Computational complexity theory, Design and analysis of algorithms. Automata and Formal languages. Cryptography. Randomness and pseudorandomness. Computational learning. Optimization. Algorithmic game theory. Distributed systems and networks. Coding and Information theory. Semantics and verification of programs. Symbolic and numeric computation. Quantum computing and information. Algorithmic and computational aspects in mathematics. Computational models and problems in the natural and social sciences.
Maria-Florina Balcan

Carnegie Mellon University, USA

Nikhil Bansal

University of Michigan, USA

Survey lecture on discrepancy theory and related algorithms

Jointly in sections 16, 18

Nikhil Bansal is the Patrick C. Fischer professor of Computer Science and Engineering at the University of Michigan, Ann Arbor. He completed his PhD from Carnegie Mellon University in 2003 and has previously worked at IBM Research, TU Eindhoven and CWI Amsterdam. He is broadly interested in theoretical computer science with focus on the design and analysis of algorithms, discrete mathematics and combinatorial optimization. Some of his notable works include understanding the algorithmic aspects of discrepancy and algorithms for the k-server problem.
Georges Gonthier

Inria - Saclay Île de France, France

Lecture on the state of the art of computer‑assisted proofs

Also in section 1

Georges Gonthier is a researcher at Inria — Saclay Île de France.
Tali Kaufman

Bar Ilan University, Israel

Tali Kaufman is a professor in the computer science department at Bar Ilan University in Israel. She is interested in stability phenomena (aka local testability) in computation. She has worked on finding mathematical phenomena that imply stability, aiming at putting stability on the solid mathematical ground. Towards that, she has studied the role of symmetry and affine invariance. Namely, the role of a group acting on an error correcting code has on its local testability properties. She is one of the pioneers of the study of high dimensional expansion in computer science and mathematics. Her work drew connections between stability of codes to the topological overlapping notion, that was introduced by Gromov. This connection has led to a resolution of a question of Gromov on the existence of bounded degree simplicial complexes with the topological overlapping property. Her study of the spectral aspects of high dimensional expansion and high dimensional random works has led to an understanding of fast mixing of Markov Chains and Glauber dynamics in situations that were previously beyond reach. Her study of the topological aspects of high dimensional expansion has led to the first efficiently decodable LDPC quantum code beyond the $\sqrt{n}$ distance barrier.
Yann LeCun

Facebook AI Research and Courant Institute of Mathematical Sciences, New York University, USA

Lecture on some of the mathematical questions raised by deep learning

Jointly in sections 17, 18

Yann LeCun is VP & Chief AI Scientist at Facebook and Silver Professor at NYU affiliated with the Courant Institute of Mathematical Sciences & the Center for Data Science.

He was the founding Director of Facebook AI Research and of the NYU Center for Data Science. He received an Engineering Diploma from ESIEE (Paris) and a PhD from Sorbonne Université.

After a postdoc in Toronto he joined AT&T Bell Labs in 1988, and AT&T Labs in 1996 as Head of Image Processing Research.

He joined NYU as a professor in 2003 and Facebook in 2013. His interests include AI machine learning, computer perception, robotics and computational neuroscience.

He is the recipient of the 2018 ACM Turing Award (with Geoffrey Hinton and Yoshua Bengio) for «conceptual and engineering breakthroughs that have made deep neural networks a critical component of computing», a member of the National Academy of Engineering and a Chevalier de la Légion d’Honneur.

Huijia (Rachel) Lin

University of Washington, USA

Lecture on obfuscation schemes

Joint lecture with Amit Sahai

Jointly in sections 1, 2

Huijia (Rachel) Lin is an Associate Professor in the Paul G. Allen School of Computer Science and Engineering at the University of Washington, where she co-leads the Cryptography Lab. Before joining the University of Washington, she was an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara.

Earlier, she obtained a PhD in Computer Science from Cornell University, and was a postdoctoral researcher at MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and Department of Computer Science at Boston University.

Her research interests are in Cryptography, and broadly its interplay with theory of computer science and security. She is known for her works on program obfuscation, functional encryption, secure multiparty computation, non-malleability and concurrent security. She is a recipient of a US National Science Foundation CAREER award, a Hellman Fellowship, a JP Morgan Faculty award, and a Microsoft Research PhD Fellowship.

She has won a best paper award honorable mention at Eurocrypt 2016, a best paper award at Eurocrypt 2018, and a best paper award at STOC 2021. Her papers have been many times invited to special issues of journals for selected papers at cryptography and theory of computing conferences, and covered by media such as the Quanta Magazine and Forbes.

Elchanan Mossel


Survey lecture on combinatorial statistics and its role in the sciences

Jointly in sections 12, 13, 18

Elchanan Mossel is a Professor of Mathematics at the Massachusetts Institute of Technology. His research spans a number of topics across probability, statistics, economics, computer science, and mathematical biology.

He is known for his work in discrete Fourier analysis and its applications to computational complexity and social choice theory and for his research of information flow in biological, economic, and inferential networks.

Mossel held a Sloan Fellowship. He is a fellow of the American Mathematical Society, a Simons Fellow and a Vannevar Bush Fellow.

Jelani Nelson

University of California Berkeley, USA

Jelani Nelson is a Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He is interested in the theory of computation broadly, with a large portion of his work focusing on algorithms for massive and high-dimensional data sets. His selected contributions include the asymptotic optimality of the Johnson-Lindenstrauss lemma (with K. G. Larsen), and optimal memory bounds for approximate counting (with H. Yu) and for estimating the number of distinct elements in a stream of items (with D. M. Kane and D. P. Woodruff), amongst several other results related to low-memory streaming algorithms and dimensionality reduction methods. He is a recipient of the Presidential Early Career Award for Scientists and Engineers, a Sloan Research Fellowship, and an NSF CAREER Award. He is also the founder and President of AddisCoder (, a 501©(3) nonprofit that has thus far trained over 500 Ethiopian high school students in algorithms, with several alumni eventually entering PhD programs in engineering and the mathematical sciences, and many others going into big tech working at companies such as AMD, Facebook, Google, and Microsoft.

Courant Institute of Mathematical Sciences, USA

Oded Regev graduated from Tel Aviv University in 2001 under the supervision of Yossi Azar. He then spent two years as a postdoc at the Institute for Advanced Study, followed by another postdoc at UC Berkeley. He held faculty positions in Tel Aviv University and the École Normale Supérieure, Paris, and since 2012 is a professor in the Computer Science Department of the Courant Institute of New York University. His work focuses on mathematical and computational aspects of point lattices, in particular, in the area of lattice-based cryptography, where he introduced the Learning with Errors (LWE) problem. He is also interested in machine learning applications in biology. He is the recipient of the 2018 Gödel Prize awarded yearly for an outstanding paper in the area of theoretical computer science, and of the 2019 Simons Investigator award, for providing a theoretical basis for quantum-resistant cryptographic protocols.
Shmuel (Muli) Safra

Tel Aviv University, Israel

Shmuel (Muli) Safra is a Professor at the School of Computer Science (in the Faculty of Exact Sciences) at Tel Aviv University, Israel. His interests include mathematics of computation (complexity theory and analysis of Boolean functions) and automata theory. His work in complexity theory includes the classification of approximation problems—showing them to be NP-hard even for weak factors of approximation—and the theory of probabilistically checkable proofs (PCP) and the PCP theorem. His earlier work on automata theory investigates determinization and complementation of finite automata over infinite strings. Safra won the Gödel Prize in theoretical computer science as well as, together with his collaborators, the Best Paper award at FOCS’18 for proving the 2-to-2-Games conjecture, recognized by the community as half the distance towards the Unique-Games conjecture. In 2019 he was awarded an ERC grant for his research on PCP and ABF. His other interests include photography.
Amit Sahai


Lecture on obfuscation schemes

Joint lecture with Huijia (Rachel) Lin

Jointly in sections 1, 2

Amit Sahai is a Fellow of the ACM (2018) and a Fellow of the IACR (2019). He is also a Fellow of the Royal Society of Arts (2021), and Advisor to the Prison Mathematics Project. He is the incumbent of the Symantec Endowed Chair in Computer Science. He received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was on the faculty at Princeton University; in 2004 he joined UCLA, where he currently holds the position of Professor of Computer Science. He serves as an editor of J. Cryptology (Springer-Nature). His research interests are in security and cryptography, and theoretical computer science more broadly. He is the co-inventor of Attribute-Based Encryption, Functional Encryption, and Indistinguishability Obfuscation. He has published more than 150 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, received an Okawa Research Grant Award in 2007, a Xerox Foundation Faculty Award in 2010, a Google Faculty Research Award in 2010, a 2012 Pazy Memorial Award, a 2016 ACM CCS Test of Time Award, a 2019 AWS Machine Learning Research Award, and a 2020 IACR Test of Time Award (Eurocrypt). For his teaching, he was given the 2016 Lockheed Martin Excellence in Teaching Award from the Samueli School of Engineering at UCLA. His research has been covered by several news agencies including the BBC World Service, Quanta Magazine, Wired, and IEEE Spectrum.
David Silver

Google DeepMind, UK

Lecture on recent breakthroughs in reinforcement learning

Also in section 17

David Silver is a distinguished research scientist at DeepMind and a professor at University College London.

David’s work focuses on artificially intelligent agents based on reinforcement learning. David co-led the project that combined deep learning and reinforcement learning to play Atari games directly from pixels (Nature 2015).

He also led the AlphaGo project, culminating in the first program to defeat a top professional player in the full-size game of Go (Nature 2016), and the AlphaZero project, which learned by itself to defeat the world’s strongest chess, shogi and Go programs (Nature 2017, Science 2018).

Most recently he co-led the AlphaStar project, which led to the world’s first grandmaster level StarCraft player (Nature 2019).

His work has been recognised by the Marvin Minsky award, Mensa Foundation Prize, and Royal Academy of Engineering Silver Medal.

Bernd Sturmfels

MPI Leipzig/ UC Berkeley, Germany/ USA

Survey lecture on applied / computational algebra

Jointly in sections 2, 13

Bernd Sturmfels is a leading experimentalist among mathematicians.

He is well-known for his contributions to computational algebraic geometry, commutative algebra, geometric combinatorics, and their applications, notably in statistics, optimization, and the lifesciences. He has authored 11 books and 270 research articles.

Sturmfels received doctoral degrees in 1987 from the University of Washingtonand the Technical University Darmstadt, and an honorary doctorate in 2015from the Goethe University Frankfurt. He joined UC Berkeley in 1995, where he is a Professor of Mathematics, Statistics and Computer Science. In 2017 he moved to the Max-Planck Institute for Mathematics in the Sciences in Leipzig, where he is a director and the head of the Nonlinear Algebra department. He is also affiliated with the Technical University Berlin and Leipzig University. Hishonors include a David and Lucile Packard Fellowship, a Humboldt Senior Research Prize, the SIAM von Neumann Lecturership, and the George David Birkhoff Prize in Applied Mathematics. He is a fellow of AMS and SIAM,and a member of the Berlin-Brandenburg Academy of Sciences.

Sturmfels is passionate about promoting outward-looking mathematics and the inclusion of talents from all backgrounds. Among his 60 doctoral students and countless postdocs, many are female. He firmly believes in excellence through diversity, and the axioms laid out by Federico Ardila.

Ola Svensson

EPFL, Switzerland

Ola Svensson is an Associate Professor at the School of Computer and Communication Sciences at EPFL, Switzerland. His interests include approximation algorithms, combinatorial optimization, combinatorics, and computational complexity. In particular, he is known for his work on the travelling salesman problem and the matching problem. His work has received several recognitions including the 2019 Michael and Sheila Held Prize by the National Academy of Sciences and best paper awards at the IEEE Symposium on Foundations of Computer Science (FOCS) and the ACM Symposium on Theory of Computing (STOC).
Thomas Vidick

California Institute of Technology, USA

Thomas Vidick is a Professor of Computing and Mathematical Sciences at the California Institute of Technology, where he is also director of the Center for the Mathematics of Information (CMI). His research is at the interface of theoretical computer science, quantum information and cryptography. He is known for his work in the theory of quantum interactive proofs, including results on device-independent cryptography, certified randomness, and the complexity of quantum multiprover interactive proof systems. The study of quantum entanglement provides a unifying goal behind all these areas and a focal point for future research.

In 2017 Vidick was named a CIFAR Azrieli Global Scholar. In 2019 he received a Presidential Early-Career Award (PECASE). In 2020 he was awarded an international research chair at INRIA.

Thu Nov 18 2021 13:43:55 GMT+0300 (Moscow Standard Time)