# SimonsTV

Our videos can also be found on YouTube.
Playlist: 45 videos

Aug. 2021

This summer, the Simons Institute hosted our first indoor research activity in sixteen months, the 2021 Summer Cluster in Quantum Computation.

In this episode of Polylogues, cluster organizer and Director for Quantum Computing Umesh Vazirani sits down with the other members of the organizing team to discuss some of the themes of the cluster: quantum complexity theory, quantum protocols and the nature of entanglement, quantum algorithms, and quantum chemistry.

Featuring: Sandy Irani (UC Irvine), James Whitfield (Dartmouth College), and Henry Yuen (Columbia University.

This production is an activity of the Simons Institute's Research Pod in Quantum Computing, and is funded by the Department of Energy (via the Quantum Systems Accelerator) and the National Science Foundation (via a Quantum Leap Challenge Institutes award).

© Simons Institute for the Theory of Computing, 2021

In this episode of Polylogues, cluster organizer and Director for Quantum Computing Umesh Vazirani sits down with the other members of the organizing team to discuss some of the themes of the cluster: quantum complexity theory, quantum protocols and the nature of entanglement, quantum algorithms, and quantum chemistry.

Featuring: Sandy Irani (UC Irvine), James Whitfield (Dartmouth College), and Henry Yuen (Columbia University.

This production is an activity of the Simons Institute's Research Pod in Quantum Computing, and is funded by the Department of Energy (via the Quantum Systems Accelerator) and the National Science Foundation (via a Quantum Leap Challenge Institutes award).

© Simons Institute for the Theory of Computing, 2021

Playlist: 21 videos

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

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

Mar. 2021

Playlist: 22 videos

Oct. 2020

Doina Precup (McGill Univeristy & MILA / DeepMind)

https://simons.berkeley.edu/talks/tbd-224

Deep Reinforcement Learning

https://simons.berkeley.edu/talks/tbd-224

Deep Reinforcement Learning

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)

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)

Apr. 2020

Theory Shorts is a documentary web series that explores topics from the Simons Institute’s research programs.

Episode 1, “Perception as Inference: The Brain and Computation,” explores the computational processes by which the brain builds visual models of the external world, based on noisy or incomplete data from patterns of light sensed on the retinae.

HOST

Bruno Olshausen

DIRECTOR

Christoph Drösser

EDITOR

Michaelle McGaraghan

PRODUCERS

Kristin Kane

Michaelle McGaraghan

SCIENTIFIC ADVISOR

Shafi Goldwasser

ANIMATORS

Caresse Haaser

Christoph Drösser

Lukas Engelhardt

GRAPHIC DESIGNER

Barry Bödeker

VIDEOGRAPHERS

Drew Mason

Omied Far

Michaelle McGaraghan

Matt Beardsley

PRODUCTION ASSISTANTS

Christine Wang

Bexia Shi

Lior Shavit

THEME MUSIC

“Plastic” by Purple Moons

Courtesy of Marmoset in Portland, Oregon

OTHER MEDIA COURTESY OF

Bruce Damonte

Arash Fazl

Anders Garm

Jean Lorenceau and Maggie Shiffrar

Beau Lotto

A. L. Yarbus

Bruno Olshausen

videocobra / Pond5

BlackBoxGuild / Pond5

nechaevkon / Pond5

DaveWeeks / Pond5

CinematicStockVideo / Pond5

BananaRepublic / Pond5

MicroStockTube / Pond5

shelllink / Pond5

AudioQuattro / Envato Market

HitsLab / Envato Market

FlossieWood / Envato Market

plaincask / Envato Market

MusicDog / Envato Market

Loopmaster / Envato Market

Ryokosan / Envato Market

Images used under license from Shutterstock.com

© Simons Institute for the Theory of Computing, 2019

Episode 1, “Perception as Inference: The Brain and Computation,” explores the computational processes by which the brain builds visual models of the external world, based on noisy or incomplete data from patterns of light sensed on the retinae.

HOST

Bruno Olshausen

DIRECTOR

Christoph Drösser

EDITOR

Michaelle McGaraghan

PRODUCERS

Kristin Kane

Michaelle McGaraghan

SCIENTIFIC ADVISOR

Shafi Goldwasser

ANIMATORS

Caresse Haaser

Christoph Drösser

Lukas Engelhardt

GRAPHIC DESIGNER

Barry Bödeker

VIDEOGRAPHERS

Drew Mason

Omied Far

Michaelle McGaraghan

Matt Beardsley

PRODUCTION ASSISTANTS

Christine Wang

Bexia Shi

Lior Shavit

THEME MUSIC

“Plastic” by Purple Moons

Courtesy of Marmoset in Portland, Oregon

OTHER MEDIA COURTESY OF

Bruce Damonte

Arash Fazl

Anders Garm

Jean Lorenceau and Maggie Shiffrar

Beau Lotto

A. L. Yarbus

Bruno Olshausen

videocobra / Pond5

BlackBoxGuild / Pond5

nechaevkon / Pond5

DaveWeeks / Pond5

CinematicStockVideo / Pond5

BananaRepublic / Pond5

MicroStockTube / Pond5

shelllink / Pond5

AudioQuattro / Envato Market

HitsLab / Envato Market

FlossieWood / Envato Market

plaincask / Envato Market

MusicDog / Envato Market

Loopmaster / Envato Market

Ryokosan / Envato Market

Images used under license from Shutterstock.com

© Simons Institute for the Theory of Computing, 2019

Playlist: 6 videos

Dec. 2019

Andrew W. Lo (Massachusetts Institute of Technology)

Theoretically Speaking Series, Fall 2019

https://simons.berkeley.edu/events/andrewlo

Theoretically Speaking Series, Fall 2019

https://simons.berkeley.edu/events/andrewlo

Aug. 2019

Zico Kolter (CMU Bosch)

https://simons.berkeley.edu/talks/integrating-constraints-deep-learning-architectures-structured-layers

Emerging Challenges in Deep Learning

https://simons.berkeley.edu/talks/integrating-constraints-deep-learning-architectures-structured-layers

Emerging Challenges in Deep Learning

Playlist: 24 videos

Playlist: 7 videos

Playlist: 9 videos

Jun. 2018

Urmila Mahadev, UC Berkeley

https://simons.berkeley.edu/talks/urmila-mahadev-06-15-18

Challenges in Quantum Computation

https://simons.berkeley.edu/talks/urmila-mahadev-06-15-18

Challenges in Quantum Computation

Jun. 2018

John Martinis, UC Santa Barbara

https://simons.berkeley.edu/talks/john-martinis-06-12-18

Challenges in Quantum Computation

https://simons.berkeley.edu/talks/john-martinis-06-12-18

Challenges in Quantum Computation

This workshop will focus on the problem of inferring structure from neuroscience data, including the following specific themes:

Playlist: 13 videos