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 [at] 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!