Simons Institute 10th Anniversary Symposium

Location

Krutch Theatre, UC Berkeley Clark Kerr Campus

Date

Wednesday, May 25 – Friday, May 27, 2022

About

Location: Krutch Theatre, UC Berkeley Clark Kerr Campus

Many thanks to those who joined us in Berkeley to celebrate a decade of collaboration and discovery at the Simons Institute! Our 10th Anniversary Symposium highlighted key research results in the theory of computing during the last ten years, and contemplated research directions for the decade to come.

The talks are now viewable on our SimonsTV YouTube channel.

Established on July 1, 2012 with a generous ten-year grant from the Simons Foundation, the Simons Institute for the Theory of Computing is the world's leading venue for collaborative research in theoretical computer science. The Simons Institute brings together the world's leading researchers in theoretical computer science and related fields, as well as the next generation of outstanding young scholars, to explore deep unsolved problems about the nature and limits of computation.

Symposium topics included coding theory, complexity, optimization, combinatorics, obfuscation, network flow, beyond worst-case analysis, adaptive data analysis, machine learning, quantum computing, game theory, blockchain, lattice cryptography, and the intersections of theoretical computer science with finance and neuroscience, to name a few.

The symposium took place in person in Berkeley.

SCHEDULE
Location: Krutch Theatre, UC Berkeley Clark Kerr Campus

Wednesday, May 25th, 2022

9 – 9:25 am		Coffee and Check-In
9:25 – 9:30 am		Welcome Shafi Goldwasser (UC Berkeley)
9:30 – 10:10 am		Modeling Conflict in Social Media Jon Kleinberg (Cornell University)
10:10 – 10:40 am		How to Obfuscate Computer Programs Mathematically Rachel Huijia Lin (University of Washington)
10:40 – 11 am		Break
11 – 11:30 am		Max-Flow and Friends, In Almost Linear Time Sushant Sachdeva (University of Toronto)
11:30 am – 12 pm		Fully Homomorphic Encryption, 10 Years Later: Definitions and Open Problems Daniele Micciancio (UC San Diego)
12 – 1:30 pm		Lunch
1:30 – 2 pm		Realizing the Promise of Neuromorphic Computing Bruno Olshausen (UC Berkeley)
2 – 2:30 pm		Patterns, Memory, and Maps: The Brain's Circuitry for Navigating the World Ila Fiete (MIT)
2:30 – 3 pm		What is the Statistical Complexity of Reinforcement Learning? Sham Kakade (Harvard University)
3 – 3:20 pm		Break
3:20 – 3:50 pm		Graphs as Geometric Objects Nati Linial (Hebrew University of Jerusalem)
3:50 – 4:35 pm		The Long Arm of Theoretical Computer Science: The Case of Blockchains/Web3 Tim Roughgarden (Columbia University)
5:30 – 7:30 pm		Welcome Reception at Calvin Lab

Thursday, May 26th, 2022

8:30 – 9 am		Coffee and Check-In
9 – 9:30 am		Expansion in Graphs, Codes, and Proofs Irit Dinur (Weizmann Institute of Science)
9:30 – 9:35 am		Break
9:35 – 10:25 am		MIP* = RE Thomas Vidick (Caltech)
10:25 – 11 am		Break
11 – 11:30 am		Connections Between Pseudorandomness and Machine Learning Russell Impagliazzo (UC San Diego)
11:30 am – 12 pm		Some New Fine-Grained Complexity Results Virginia Vassilevska Williams (MIT)
12 – 1:30 pm		Lunch Panel Discussion: History of the Institute (12:30 – 1:15 pm) Peter Bartlett (UC Berkeley), Shafi Goldwasser (UC Berkeley), Kristin Kane (moderator, UC Berkeley), Dick Karp (UC Berkeley), Christos Papadimitriou (Columbia), Melissa Nidever (UC Berkeley), Shankar Sastry (UC Berkeley), Umesh Vazirani (UC Berkeley)
1:30 – 2 pm		Is There a Framework for Deep Learning in Multi-Agent Settings? Constantinos Daskalakis (MIT)
2 – 2:30 pm		Coding Theory for Storage and Computation Mary Wootters (Stanford)
2:30 – 3 pm		A Theory of Unsupervised Machine Translation with Application to Understanding Whale Communication Adam Kalai (Microsoft Research)
3 – 3:20 pm		Break
3:20 – 3:50 pm		Continuous Algorithms: Sampling and Optimization in High Dimension Santosh Vempala (Georgia Tech)
3:50 – 4:50 pm		Panel Discussion: Beyond Worst-Case Analysis Russell Impagliazzo (moderator, UCSD), Ravi Kannan (Microsoft Research), Shang-Hua Teng (USC), Avrim Blum (TTIC), Santosh Vempala (Georgia Tech), Piotr Indyk (MIT)

Friday, May 27th, 2022

9 – 9:30 am		Coffee and Check-In
9:30 – 10:10 am		WE, THE PEOPLE, AGREE Silvio Micali (MIT and Algorand)
10:10 – 10:40 am		Replicability, Pseudodeterminism, and Proofs Toniann Pitassi (Columbia University)
10:40 – 11 am		Break
11 – 11:30 am		Fragile Algorithms and Fallible Decision-Makers Sendhil Mullainathan (University of Chicago)
11:30 am – 12 pm		Log-Concavity in Matroids and Expanders Cynthia Vinzant (University of Washington)
12 – 1:30 pm		Lunch
1:30 – 2:10 pm		How Does the Brain Create Language? Christos Papadimitriou (Columbia University)
2:10 – 2:40 pm		Questions of Scientific Validity in Machine Learning Moritz Hardt (Max Planck Institute)
2:40 – 3:40 pm		Panel Discussion: Industry and Theory Mike Luby (moderator, BitRipple), Ravi Kumar (Google), Vitaly Feldman (Apple), Silvio Micali (Algorand), Yael Kalai (Microsoft Research), Parikshit Gopalan (Apple), Mariana P. Raykova (Google)

Please direct any questions to Simons Institute events staff at simonsevents@berkeley.edu.

Check out our 10th anniversary on social media
We will be remembering key moments from our first decade throughout our anniversary season...

… and offering ways for you to get a specially designed commemorative tee-shirt!

Support our Annual Fund
Support our community fund to enable the expanding reach of our research and convenings
…and make a permanent imprint on the Institute’s next decade!