SimonsTV

Our videos can also be found on YouTube.

Tuesday, Nov. 12 – Friday, Nov. 15, 2024
Playlist: 25 videos
Monday, June 17 – Friday, June 21, 2024
Playlist: 24 videos
May. 2022
Nati Linial (Hebrew University of Jerusalem)
Simons Institute 10th Anniversary Symposium
Jan. 2022
Dylan Foster (Microsoft Research)
https://simons.berkeley.edu/talks/reinforcement-learning-part-i
Learning and Games Boot Camp
Jul. 2021
Theory Shorts is a documentary web series that explores topics from the Simons Institute’s research programs.

The second short film in the series, “Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity,” explores how we know that a problem is impossible to solve.

FURTHER READING
Fruit game optimal algorithm: Hossein Jowhari, Mert Saglam, Gábor Tardos. "Tight bounds for Lp
samplers, finding duplicates in streams, and related problems." PODS 2011: 49-58.

Fruit game optimal lower bound: Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh. "Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams." FOCS 2017: 475-486.

FEATURING
Paul Beame
Faith Ellen
Jelani Nelson
Manuel Sabin
Madhu Sudan

DIRECTORS
Anil Ananthaswamy
Kristin Kane

SCIENTIFIC ADVISOR
Shafi Goldwasser

HOST/WRITER
Anil Ananthaswamy

EDITOR/PRODUCER
Kristin Kane

GRAPHIC AND ANIMATION DESIGNER
Barry Bödeker

ANIMATORS
Caresse Haaser
Kristin Kane

VIDEOGRAPHER
Drew Mason

PRODUCTION ASSISTANTS
Kevin Hung
Bexia Shi

COPY EDITOR
Preeti Aroon

TECH SUPPORT
Adriel Olmos

SPECIAL THANKS
Ryan Adams
Wesley Adams
Marco Carmosino
Kani Ilangovan
Sampath Kannan
Richard Karp
David Kim
Bryan Nelson
Jeremy Perlman
Kat Quigley
Siobhan Roberts
Amelia Saul
Umesh Vazirani

MUSIC
Dill Pickles (Heftone Banjo Orchestra)
Flamenco Rhythm (Sunsearcher)
Place Pigalle (Uncle Skeleton)
Plastic (Purple Moons)

SOUND EFFECTS
Courtesy of byxorna, inspectorj, janbezouska, jorickhoofd, kash15, kyster, robinhood76, smotasmr, svarvarn, and vandrandepinnen via Freesound.org

OTHER MEDIA
Becoming (Jan van IJken)
A Decade of Sun (Solar Dynamics Observatory, NASA)
Move Mountain (Kirsten Lepore)

© Simons Institute for the Theory of Computing, 2021
May. 2020
The Women of Theory of Computer Science rock to our version of I Will Survive!
WIT: https://womenintheory.wordpress.com/


I Will Survive
Lyrics: Avi Wigderson (IAS)

At first I was afraid, I was petrified
I worried I could never fit this proof on just one slide
But then I spent so many nights thinking why it is so long
And I grew strong
And learned exactly what went wrong

A problem wor-thy, of attack
Just proves its worth by vigorously fighting back
I should have used error correction, should have sampled yet again
I should have stayed the course and found there is so much that I can gain

So do come back, problems galore
I am much more ready to attack you than I was before
I’ll fight you guiltless when at work, forget you guiltless when at home
And if you’re fun then in the pastures of the TCS we’ll roam

So I’ll survive, and I will thrive,
By Nash’s equilibrium, there must be balance to my life
I’ve got all my life to live,
And I’ve got all my Math to give
So I’ll survive,
and I will thrive, hey, hey

It took all the strength I had, I was nearly spent,
Trying hard to mend, the errors, in my argument
I put each pigeon in its hole, consulted every oracle
My upper bound
Turned up below my lower bound

Then I came up, with something new
I thought outside the blackbox, found what others never knew
That polynomials with a small degree have small number of roots
That few cryptogra-phic assumptions no one’s likely to dispute

So do come back, problems galore
I am much more ready to attack you than I was before
As I have wit and I have WIT and having both is pretty neat
Indeed a convex combination that is very hard to beat

So I’ll survive, and I will thrive,
Because (in theory, at least) this is a perfect life
You pick the problems that you love
To fit your brain just like a glove
So I’ll survive,
and I will thrive, hey, hey

Singers:
Dahlia Malkhi (Calibra, Facebook)
Elette Boyle (IDC, Israel)
Irit Dveer Dinur (Weizmann Institute, Israel)
Julia Chuzhoy (Toyota Technological Institute at Chicago, USA)
Katrina Ligett (Hebrew University, Israel)
Keren Censor-Hillel (Technion, Israel)
Lisa Zhang (Bell-Labs, USA)
Mary Wooters (Stanford University, USA)
Michal Feldman (Tel-Aviv University, Israel)
Nicole Immorlica (Microsoft Research, New England, USA)
Orna Kupferman (Hebrew University, Israel)
Rebecca Wright (Barnard College, USA)
Ronitt Rubinfeld (MIT, USA)
Shafi Goldwasser (Simons Institute at UC Berkeley, USA)
Shubhangi Saraf (Rutgers University, USA)
Shuchi Chawla (University of Wisconsin, Madison, USA)
Sofya Raskhodnikova (Boston University, USA)
Tal Malkin (Columbia University, USA)
Tal Rabin (Algorand Foundation, USA)
Yael Tauman Kalai (Microsoft Research, New England, USA)
Playlist: 21 videos
Playlist: 21 videos
Playlist: 20 videos
Mar. 2018
Christian Machens, Champalimaud Research
https://simons.berkeley.edu/talks/christian-machens-3-21-18
Targeted Discovery in Brain Data
Iterative methods have been greatly influential in continuous optimization. In fact, almost all algorithms in that field are iterative in nature. Recently, a confluence of ideas from optimization and theoretical computer science has led to breakthroughs in terms of new understanding and running time bound improvements for some of the classic iterative continuous optimization primitives. In this workshop we explore these advances as well as new directions that they have opened up. Some of the specific topics that this workshop plans to cover are: advanced first-order methods (non-smooth optimization, regularization and preconditioning), structured optimization, fast LP/SDP solvers, advances in interior point methods and fast streaming/sketching techniques. One of the key themes that will be highlighted is how combining the continuous and discrete points of view can often allow one to achieve near-optimal running time bounds.
Playlist: 23 videos
Much of the progress in solving discrete optimization problems, especially in terms of approximation algorithms, has come from designing novel continuous relaxations. The primary tools in this area are linear programming and semidefinite programming. Other forms of relaxations have also been developed, such as multilinear relaxation for submodular optimization. In this workshop, we explore the state-of-the-art techniques for performing discrete optimization based on continuous relaxations of the underlying problem, as well as our current understanding of the limitations of this kind of approach. We focus on LP/SDP relaxations and techniques for rounding their solutions, as well as methods for submodular optimization, both in the offline and online setting. We also investigate the limits of such relaxations and hardness of approximation results.
Playlist: 28 videos
Jan. 2017
Sergey Levine, UC Berkeley
https://simons.berkeley.edu/talks/sergey-levine-01-24-2017-1
Foundations of Machine Learning Boot Camp
The classic area of online algorithms requires us to make decisions over time as the input is slowly revealed, without (complete) knowledge of the future. This has been widely studied, e.g., in the competitive analysis model ­­­and, in parallel, in the model of regret minimization. Another widely studied setting incorporates stochastic uncertainty about the input; this uncertainty reduces over time, but postponing decisions is either costly or impossible. Problems of interest include stochastic optimization, stochastic scheduling and queueing problems, bandit problems in learning, dynamic auctions in mechanism design, secretary problems, and prophet inequalities. Recent developments have shown connections between these models, with new algorithms that interpolate between these settings and combine different techniques. The goal of the workshop is to bring together researchers working on these topics, from areas such as online algorithms, machine learning, queueing theory, mechanism design, and operations research, to exchange ideas and techniques and forge deeper connections.
Playlist: 30 videos
Apr. 11 – Apr. 15, 2016
Playlist: 28 videos
Mar. 7 – Mar. 10, 2016
Playlist: 26 videos
Dec. 2015
Richard Karp sat down with Tim Roughgarden to discuss the Fall 2015 program on Economics and Computation.

https://simons.berkeley.edu/programs/economics2015
Nov. 2015
Tuomas Sandholm, Carnegie Mellon University
Algorithmic Game Theory and Practice
https://simons.berkeley.edu/talks/tuomas-sandholm-2015-11-18