SimonsTV

Our videos can also be found on YouTube.
Error-Correcting Codes: Theory and Practice Boot Camp
The boot camp is intended to acquaint program participants with the key themes of the program. It will consist of five days of tutorial presentations from leading experts in the topics of the program.
Playlist: 19 videos
1.
Algebraic Codes/Algorithms I
Mary Wootters (Stanford University)
2.
Algebraic Codes/Algorithms II
Mary Wootters (Stanford University)
3.
Intro to Quantum Codes
John Wright (UC Berkeley)
4.
Quantum LDPC Codes I
Nikolas Breuckmann (University of Bristol)
5.
Recent Advances in Multiplicity Codes
Prahladh Harsha (Tata Institute of Fundamental Research)
6.
Quantum LDPC Codes II
Nikolas Breuckmann (University of Bristol)
7.
Locality I
Elena Grigorescu (Purdue University)
8.
Locality II
Elena Grigorescu (Purdue University)
9.
Probabilistic and Cominatorial Methods I
Jonathan Mosheiff (Ben-Gurion University)
10.
Private video
11.
Private video
12.
Recent Advances in LTCs
Prahladh Harsha (Tata Institute of Fundamental Research)
13.
Probabilistic and Cominatorial Methods II
Jonathan Mosheiff (Ben-Gurion University)
14.
Probabilistic and Cominatorial Methods III
Jonathan Mosheiff (Ben-Gurion University)
15.
Quantum Codes in Quantum Complexity
Chinmay Nirkhe (IBM Quantum)
16.
Speed Talks
17.
Polar Codes
Hsin-Po Wang (UC Berkeley)
18.
Polar Codes
Hsin-Po Wang (UC Berkeley)
19.
Speed Talks
Beyond the Boolean Cube
Playlist: 18 videos
1.
Explicit Orthogonal and Unitary Designs
Ryan O'Donnell (Carnegie Mellon University)
2.
Reverse Hypercotractivity and Improved Sampling in High Dimensional Expanders
Yotam Dikstein (Weizmann Institute of Science)
3.
Hypercontractivity Inequality on $\varepsilon$-product Spaces
Siqi Liu (UC Berkeley)
4.
Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
Max Hopkins (UC San Diego)
5.
Product Mixing, Quantum Separation, and Comfortable Juntas
Noam Lifshitz (Hebrew University)
6.
Small-Set Expansion in the 2-Degree Short-Code Graph, the Easier Version
Guy Kindler (Hebrew University of Jerusalem)
7.
Unique Games and Expansion
Mitali Bafna (Carnegie Mellon University)
8.
Parallel Discrete Sampling via Continuous Walks
Nima Anari (Stanford University)
9.
Strong Bounds for 3-Progressions
Zander Kelley (University of Illinois Urbana-Champaign)
10.
Fractional Pseudorandom Generators
Pooya Hatami (Ohio State University)
11.
Noise Stability - Beyond the Boolean cube
Dan Mikulincer (MIT)
12.
Separating Quantum from Classical with k-fold Forrelation and Friends
Makrand Sinha (Simons Institute)
13.
It ain't over till it's over
Pei Wu (Institute for Advanced Study)
14.
Sparsifying Sums of Norms
Yang Liu (LBNL)
15.
Linearity Testing over the Biased Cube
Amey Bhangale (The Weizmann Institute of Science)
16.
Localization Schemes
Yuansi Chen (Duke University)
17.
On Perfectly Friendly Bisections of Random Graphs
Mehtaab Sawhney (MIT)
18.
Representation Theory in TCS and Extremal Combinatorics
Nathan Lindzey (Technion - Israel Institute of Technology)
Building Human Intelligence at Scale, to Save the Next Generation from ChatGPT
Apr. 2023
Po-Shen Loh (Carnegie Mellon University)
https://simons.berkeley.edu/events/theoretically-speaking-building-human-intelligence-scale-save-next-generation-chatgpt
Theoretically Speaking

The scale of global societal problems looks daunting. One person, or even a small team, is minuscule relative to the number of people who need help. For example, since ChatGPT has exploded onto the scene, our children's future employment prospects (and current educational experience, with ChatGPT-powered cheating) are in existential danger. There is an area close to mathematics, however, which devises solutions in which problems solve themselves even through self-serving human behavior: game theory.

Po-Shen Loh is a math professor, researcher, and educator who transitioned to devise new solutions for large-scale real-world problems. He will talk about his experience going between the ivory tower of academia and the practicality of the real world, where he ultimately innovated fundamentally new approaches to pandemic control (https://novid.org) and scalable advanced live math education (https://live.poshenloh.com).

He will also discuss educational strategies that build relevant skills to survive this new era of Generative AI (e.g. ChatGPT). He has been working extensively on that problem, and draws from experience teaching across the entire spectrum, from underprivileged schools to the International Math Olympiad.

Po-Shen Loh is a social entrepreneur and inventor working across the spectrum of mathematics, education, and healthcare, all around the world. He is a math professor at Carnegie Mellon University, and the national coach of the USA International Mathematical Olympiad team. He holds math degrees from Caltech and Cambridge, and a PhD from Princeton. As an academic, Po-Shen has earned distinctions ranging from an International Mathematical Olympiad silver medal to the United States Presidential Early Career Award for Scientists and Engineers. He was the coach of Carnegie Mellon University’s math team when it achieved its first-ever #1 rank among all North American universities, and the coach of the USA Math Olympiad team when it achieved its first-ever back-to-back #1-rank victories in 2015 and 2016, and then again in 2018 and 2019. His research and educational outreach takes him to cities across the world, reaching over 10,000 people each year through public lectures and events, and he has featured in or co-created videos totaling over 19 million YouTube views.
Learning In The Presence Of Strategic Agents: Dynamics, Equilibria, And Convergence
Feb. 2022
Eric Mazumdar (Caltech)
https://simons.berkeley.edu/talks/learning-presence-strategic-agents-dynamics-equilibria-and-convergence
Meet the Fellows Welcome Event
Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity | Theory Shorts
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
Theoretical Foundations of SAT/SMT Solving
Playlist: 52 videos
1.
Private video
2.
Private video
3.
Private video
4.
Encodings Showcase
https://simons.berkeley.edu/talks/encodings-showcase
5.
Private video
6.
Private video
7.
Non-CDCL Solvers
Marijn Heule (Carnegie Mellon University), Jakob Nordstrom (University of Copenhagen & Lund University), and Zhiwei Zhang (Rice University)
8.
Private video
9.
Finite Model Theory
Albert Atserias (UPC Barcelona), Benedikt Pago (Rwth Aachen University), and Antonina Kolokolova (Memorial University of Newfoundland)
10.
SAT and Foundations of Mathematics
Sasha Razborov (University of Chicago), Pavel Pudlák (Czech Academy of Sciences), and Shai Ben-David (University of Waterloo)
11.
Computer Algebra and SAT for Mathematical Search
Curtis Bright (University of Windsor)
12.
Symbolic Computation Techniques in SMT Solving: Mathematical Beauty Meets Efficient Heuristics
Erika Abraham (RWTH Aachen University)
13.
An Automated Approach to the Collatz Conjecture
Emre Yolcu (Carnegie Mellon University)
14.
Past and Present of Descriptive Complexity Theory
Albert Atserias (UPC Barcelona)
15.
A Finite-Model-Theoretic View on Propositional Proof Complexity
Benedikt Pago (Rwth Aachen University)
16.
Reasoning Systems from Descriptive Complexity
Antonina Kolokolova (Memorial University of Newfoundland)
17.
Predicting Satisfiability at the Phase Transition via End-to-End Learning
Kevin Leyton Brown (University of British Columbia)
18.
Learning to Schedule Heuristics in Branch and Bound
Elias Khalil (University of Toronto)
19.
Extensions of CDCL Branching Heuristics by Exploration during Conflict Depression
Md. Solimul Chowdhury (University of Alberta)
20.
Learning to Solve SMT Formulas
Mislav Balunović (ETH Zurich)
21.
P, NP and Proof Complexity
Sasha Razborov (University of Chicago)
22.
TAUT, TFNP and SAT
Pavel Pudlák (Czech Academy of Sciences)
23.
Can the PvsNP Question Be Independent of the Axioms of Mathematical Reasoning?
Shai Ben-David (University of Waterloo)
24.
Predicting Satisfiability at the Phase Transition via End-to-End Learning
Kevin Leyton Brown (University of British Columbia)
25.
Preprocessing SAT, MaxSAT, and QBF 1
Benjamin Kiesl (SAP)
26.
Preprocessing SAT, MaxSAT, and QBF 2
Jeremias Berg (University of Helsinki)
27.
Preprocessing SAT, MaxSAT, and QBF 3
Martina Seidl (Johannes Kepler University)
28.
Unifying Logical and Statistical AI with Markov Logic
Pedro Domingos (University of Washington)
29.
Training Neural Networks with a Little Help from Knowledge
Vivek Srikumar (University of Utah)
30.
DL2: Training and Querying Neural Networks with Logic
Marc Fischer (ETH Zurich)
31.
Constrained Gradient Descent Algorithm for Testing Neural Networks
Vineel Nagisetty (University of Waterloo)
32.
Perspectives on Practice and Theory of SAT Solving
Vijay Ganesh (University of Waterloo)
33.
On Using Structural Properties to Improve CDCL Solver Performance
David Mitchell (Simon Fraser University)
34.
Towards an (Experimental) Understanding of SAT Solvers
Laurent Simon (Bordeaux INP)
35.
On the Formal Characterization of Industrial SAT Instances
Jordi Levy (Artificial Intelligence Research Institute, Spanish National Research Council)
36.
Algorithmic utilization of structure in SAT instances
Stefan Szeidar (TU Wien)
37.
Structural Parameters - Heterogeneity and Geometry
Ralf Rothenberger (University of Potsdam)
38.
Representing problems to SAT solvers: basic theory, basic questions
Oliver Kullmann (Swansea University)
39.
Advantages and limitations of Dual-Rail MaxSAT
Maria Bonet (Universitat Politècnica de Catalunya)
40.
Encodings and Consistency from a Constraint Programming Perspective
Ciaran McCreesh (University of Glasgow)
41.
Proof Complexity meets Finite Model Theory
Joanna Ochremiak (CNRS)
42.
Hard Formulas in Proof Complexity by Composition
Robert Robere (McGill University)
43.
Non-Automatability: When Finding Proofs Is Provably Hard
Susanna de Rezende (Czech Academy of Sciences)
44.
Using Resolution and Cutting Planes for Verification of Nonlinear Bit-Vector Properties
Paul Beame (University of Washington)
45.
Hard Examples for Common Variable Decision Heuristics
Marc Vinyals (Technion - Israel Institute of Technology)
46.
The Proof Complexity of Integer Programming
Noah Fleming (University of Toronto),
47.
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Chunxiao (Ian) Li (University of Waterloo)
48.
Look-ahead SAT Solvers: Smart vs. Fast
Marijn Heule (Carnegie Mellon University)
49.
Searching Inside the Box: A Continuous-Local-Search Approach for Hybrid SAT Solving
Zhiwei Zhang (Rice University)
50.
Pseudo-Boolean Solving: In Between SAT and ILP
Jakob Nordstrom (University of Copenhagen & Lund University)
Quantum Colloquium
This colloquium series features talks by some of the foremost experts in quantum computation in the form of "an invitation to research in area X". With the explosion of interest in quantum computation, there is a dizzying flurry of results, as well as a diverse group of researchers who are drawn to this field. This colloquium series aims to target three audiences:
Playlist: 70 videos
1.
How to Locate Unentanglement | Quantum Colloquium
John Wright (U.C. Berkeley)
2.
Magic State Cultivation | Quantum Colloquium
Craig Gidney (Google)
3.
How to Build a Quantum Supercomputer: Scaling from Hundreds to Millions of Qubits | Quantum Coll.
John Martinis (Qolab)
4.
The Jacobi Factoring Circuit: Classically Hard Factoring in Sublinear Quantum Space and Depth
Seyoon Ragavan (MIT)
5.
How to Construct Random Unitaries | Quantum Colloquium
Fermi Ma (Simons Institute)
6.
Optimization by Decoded Quantum Interferometry | Quantum Colloquium
Stephen Jordan (Google)
7.
Transversal Algorithmic Fault Tolerance for Low-Overhead Quantum Computing | Quantum Colloquium
Hengyun (Harry), Zhou (QuEra)
8.
Random Unitaries in Extremely Low Depth | Quantum Colloquium
Robert Huang (Google, Caltech)
9.
An Efficient Quantum Factoring Algorithm | Quantum Colloquium
Oded Regev (NYU)
10.
Logical Quantum Processor Based On Reconfigurable Atom Arrays | Quantum Colloquium
Dolev Bluvstein (Harvard)
11.
Phase Transition in Random Circuit Sampling | Quantum Colloquium
Sergio Boixo (Google) & Kostyantyn Kechedzhi (Google)
12.
The Power of Unentangled Quantum Proofs With Non-negative Amplitudes | Quantum Colloquium
Pei Wu (IAS)
13.
Quantum Pseudoentanglement | Quantum Colloquium
Adam Bouland (Stanford University)
14.
Efficient Quantum Gibbs Samplers | Quantum Colloquium
Chi Fang (Anthony) Chen (Caltech)
15.
The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium
Chris (Jielun) Chen (Caltech)
16.
NLTS Hamiltonians from Codes — Panel | Quantum Colloquium
Panel Discussion: Anand Natarajan (MIT), Dorit Aharonov (Hebrew University) and Matt Hastings (Microsoft Research); Umesh Vazirani (UC Berkeley; moderator).
17.
Approaching the Quantum Singleton Bound with Approximate Error Correction
Sam Gunn (UC Berkeley)
18.
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Yunchao Liu (UC Berkeley)
19.
Learning to Predict Arbitrary Quantum Processes
Hsin-Yuan Huang (Caltech)
20.
Linear Growth of Quantum Circuit Complexity
Jens Eisert (Free University of Berlin)
21.
NLTS Hamiltonians from Codes | Quantum Colloquium
Chinmay Nirkhe (IBM Research)
22.
Black Holes and the Quantum-Extended Church-Turing Thesis | Quantum Colloquium
Leonard Susskind (Stanford University)
23.
Efficient Error Correction in Neutral Atoms via Erasure Conversion | Quantum Colloquium
Jeff Thompson (Princeton)
24.
The Quantum LDPC Manifesto | Quantum Colloquium
Anthony Leverrier (INRIA)
25.
Quantum Colloquium – Panel
Panel featuring Yael Kalai (Microsoft Research), Vinod Vaikuntanathan (MIT), and Thomas Vidick (Caltech); Umesh Vazirani (UC Berkeley; moderator).
26.
Verifiable Quantum Advantage Without Structure | Quantum Colloquium
Mark Zhandry (Princeton)
27.
Panel | Quantum Colloquium
Panel featuring Lin Lin (UC Berkeley), Birgitta Whaley (UC Berkeley), James Whitfield (Dartmouth), and Nathan Wiebe (University of Toronto); Umesh Vazirani (UC Berkeley; moderator).
28.
Is There Evidence of Exponential Quantum Advantage in Quantum Chemistry? | Quantum Colloquium
Garnet Chan (Caltech)
29.
Panel | Quantum Colloquium
Panel featuring Sergio Boixo (Google), Soonwon Choi (MIT), and Bill Fefferman (University of Chicago); Umesh Vazirani (UC Berkeley; moderator).
30.
On the Limits for Certifying Quantum Speedups for Noisy Circuits | Quantum Colloquium
Boaz Barak (Harvard University)
31.
Panel on Making Predictions in a Quantum World | Quantum Colloquium
Panel featuring Scott Aaronson (UT Austin), Dorit Aharonov (Hebrew University), Ignacio Cirac (Max Planck Institute of Quantum Optics), Elad Hazan (Princeton). Umesh Vazirani (UC Berkeley; moderator).
32.
Making Predictions in a Quantum World | Quantum Colloquium
Hsin-Yuan Huang (Caltech)
33.
Panel on Verifiable Quantum Advantage | Quantum Colloquium
Panel featuring Chris Monroe (Duke University), Lieven Vandersypen (TU Delft), Mark Zhandry (Princeton University), and Umesh Vazirani (UC Berkeley; moderator).
34.
Interactive Protocols for Classically-Verifiable Quantum Advantage with an Ion-Trap Quantum Computer
Andru Gheorghiu (ETH Zürich) and Daiwei Zhu (University of Maryland)
35.
Panel Discussion: Exploring New Scientific Frontiers with Programmable Quantum Simulators
Panel featuring Andrew Childs (University of Maryland), Norman Yao (UC Berkeley), Markus Greiner (Harvard University), Monika Aidelsburger (University of Munich), and Umesh Vazirani (UC Berkeley; moderator).
36.
Panel on Novel Fault-Tolerant Qubits | Quantum Colloquium
Panel featuring Amir Safavi-Naeini (Stanford University), Daniel Litinski (PsiQuantum), Robert Raussendorf (University of British Columbia), and Umesh Vazirani (UC Berkeley; moderator).
37.
Simple Architecture for a Fault-Tolerant Qubit | Quantum Colloquium
Patrick Hayden (Stanford University)
38.
Panel on Bosonic Error Correction Codes | Quantum Colloquium
Panel featuring Daniel Gottesman (University of Maryland), Shruti Puri (Yale University), Jonathan Home (ETH Zurich), Chen Wang (UMass Amherst), and Umesh Vazirani (UC Berkeley; moderator).
39.
An Error-Corrected Logical Quantum Bit Encoded in Grid States of a Superconducting Cavity
Michel Devoret (Yale University)
40.
Panel on Quantum Machine Learning and Barren Plateaus | Quantum Colloquium
Panel featuring Patrick Coles (Los Alamos National Labs), Aram Harrow (MIT), Maria Schuld (UKZN and Xanadu), and Umesh Vazirani (UC Berkeley; moderator).
41.
Barren Plateaus and Quantum Generative Training Using Rényi Divergences | Quantum Colloquium
Nathan Wiebe (University of Toronto)
42.
Panel on Securing Cryptography Against Quantum Adversaries | Quantum Colloquium
Zvika Brakerski (Weizmann Institute), Anne Broadbent (U. Ottawa), Yael Kalai (Microsoft Research) and Umesh Vazirani (UC Berkeley; moderator)
43.
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier | Quantum Colloquium
Fermi Ma (Simons Institute)
44.
Panel on Quantum Interactive Dynamics | Quantum Colloquium
Adam Nahum (I'Ecole Normale Supérieure), Pedram Roushan (Google), Barbara Terhal (TU Delft), and Umesh Vazirani (UC Berkeley; moderator)
45.
Towards a Quantum Interactive Dynamics | Quantum Colloquium
Shivaji Sondhi (Oxford University)
46.
Panel on Lattice Algorithms and Cryptography
Panel featuring Lior Eldar (MIT), Vinod Vaikuntanathan (MIT), Daniel Apon (NIST), Umesh Vazirani (UC Berkeley; moderator)
47.
An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor
Sean Hallgren (Penn State University & Senior Visitor at Simons Institute 2021-22)
48.
Panel Discussion on Quantum Algorithms for Optimization | Quantum Colloquium
Eddie Farhi (MIT/Google), Ashley Montanaro (U. Bristol), Umesh Vazirani (UC Berkeley; moderator)
49.
Quantum Algorithms for Optimization | Quantum Colloquium
Ronald de Wolf (QuSoft, CWI and University of Amsterdam)
50.
Panel Discussion on The Role of Proofs in MIP* = RE | Quantum Colloquium
Marius Junge (UIUC), William Slofstra (Univ of Waterloo), Umesh Vazirani (UC Berkeley; moderator)
Satisfiability: Theory, Practice, and Beyond Boot Camp
Playlist: 22 videos
1.
Dancing Around SAT 1
Valentine Kabanets (Simon Fraser University)
2.
Dancing Around SAT 2
Valentine Kabanets (Simon Fraser University)
3.
Dancing Around SAT 3
Valentine Kabanets (Simon Fraser University)
4.
Dancing Around SAT 4
Valentine Kabanets (Simon Fraser University)
5.
Dancing Around SAT 5
Valentine Kabanets (Simon Fraser University)
6.
Dancing Around SAT 6
Valentine Kabanets (Simon Fraser University)
7.
Proof Complexity A
Sam Buss (UC San Diego)
8.
Proof Complexity B
Sam Buss (UC San Diego)
9.
Proof Complexity D
Sam Buss (UC San Diego)
10.
SAT-Solving
Armin Biere (Johannes Kepler University)
11.
SAT-Centered Complexity Theory
Valentine Kabanets (Simon Fraser University)
12.
Proof Complexity C
Sam Buss (UC San Diego)
13.
SAT-Solving
Armin Biere (Johannes Kepler University)
14.
Proof Complexity
Sam Buss (UC San Diego)
15.
Pseudo-Boolean Solving and Optimization
Jakob Nordström (University of Copenhagen & Lund University)
16.
Pseudo-Boolean Solving and Optimization 1
Jakob Nordström (University of Copenhagen & Lund University)
17.
Pseudo-Boolean Solving and Optimization 2
Jakob Nordström (University of Copenhagen & Lund University)
18.
Pseudo-Boolean Solving and Optimization 3
Jakob Nordström (University of Copenhagen & Lund University)
19.
Pseudo-Boolean Solving and Optimization 4
Jakob Nordström (University of Copenhagen & Lund University)
20.
Approximate Counting and Sampling
Kuldeep Meel (National University of Singapore)
21.
Programming Z3
Nikolaj Björner (Microsoft Research)
22.
Using SAT Solvers to Prevent Causal Failures in the Cloud
Ruzica Piskac (Yale University)
Perception as Inference: The Brain and Computation | Theory Shorts
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
Geometry of Polynomials Boot Camp
Playlist: 27 videos
1.
Real-Rooted Polynomials
Jan Vondrák (Stanford University)
2.
Real-Rooted Polynomials (problem session)
Jan Vondrák (Stanford University)
3.
Real Stable Polynomials, Strongly Rayleigh Distributions, and Applications, Part I-A
Shayan Oveis Gharan (University of Washington)
4.
Real Stable Polynomials, Strongly Rayleigh Distributions, and Applications, Part I-B
Shayan Oveis Gharan (University of Washington)
5.
The Method of Interlacing Polynomials - A
Jan Vondrák (Stanford University)
6.
The Method of Interlacing Polynomials - B
Jan Vondrák (Stanford University)
7.
Ramanujan Graphs, Treelike Walks, and Mixed Characteristic Polynomials - A
Nikhil Srivastava (UC Berkeley)
8.
Ramanujan Graphs, Treelike Walks, and Mixed Characteristic Polynomials - B
Nikhil Srivastava (UC Berkeley)
9.
The Barrier Method and the Kadison-Singer Problem - A
Nikhil Srivastava (UC Berkeley)
10.
The Barrier Method and the Kadison-Singer Problem - B
Nikhil Srivastava (UC Berkeley)
11.
Real Stable Polynomials, Strongly Rayleigh Distributions, and Applications, Part II - A
Shayan Oveis Gharan (University of Washington)
12.
Real Stable Polynomials, Strongly Rayleigh Distributions, and Applications, Part II - B
Shayan Oveis Gharan (University of Washington)
13.
Hyperbolic Optimization, Part I - A
Michel Goemans (Massachusetts Institute of Technology)
14.
Hyperbolic Optimization, Part I - B
Michel Goemans (Massachusetts Institute of Technology)
15.
Hyperbolic Optimization, Part II
Michel Goemans (Massachusetts Institute of Technology)
16.
Computing Partition Functions by Polynomial Interpolation, Part II - A
Alexander Barvinok (University of Michigan)
17.
Computing Partition Functions by Polynomial Interpolation, Part I - B
Alexander Barvinok (University of Michigan)
18.
Hyperbolic Polynomials and Determinantal Representations, Part I
Rainer Sinn (Freie Universität Berlin)
19.
Hyperbolic Polynomials and Determinantal Representations, Part II - A
Rainer Sinn (Freie Universität Berlin)
20.
Hyperbolic Polynomials and Determinantal Representations, Part I - B
Rainer Sinn (Freie Universität Berlin)
21.
Computing Partition Functions, Part I
Alistair Sinclair (UC Berkeley)
22.
Computing Partition Functions, Part II - partial 1
Alistair Sinclair (UC Berkeley)
23.
Computing Partition Functions, Part II - partial 2
Alistair Sinclair (UC Berkeley)
24.
Completely Log-Concave Polynomials and Distributions, Part I - A
Nima Anari (Stanford University)
25.
Completely Log-Concave Polynomials and Distributions, Part I - B
Nima Anari (Stanford University)
26.
Completely Log-Concave Polynomials and Distributions, Part II - A
Nima Anari (Stanford University)
27.
Completely Log-Concave Polynomials and Distributions, Part II - B
Nima Anari (Stanford University)
Can Non-Convex Optimization be Robust?
Nov. 2018
Rong Ge (Duke University)
https://simons.berkeley.edu/talks/can-non-convex-optimization-be-robust
Robust and High-Dimensional Statistics
Cortical Areas Interact through a Communication Subspace
Mar. 2018
Christian Machens, Champalimaud Research
https://simons.berkeley.edu/talks/christian-machens-3-21-18
Targeted Discovery in Brain Data
Fast Iterative Methods in Optimization
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
1.
Continuous Methods for Discrete Optimization: From Convex Relaxations, to Iterative Schemes...
Aleksander Mądry, MIT
2.
Width-independent Iterative Algorithms for Packing and Covering Programs
Lorenzo Orecchia, Boston University
3.
Slime Molds and Sparse Recovery
Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne
4.
Michael Cohen and ell_p Regression
Yin-Tat Lee, University of Washington
5.
Chordal Graphs and Sparse Semidefinite Optimization
Lieven Vandenberghe, UCLA
6.
On the Optimization Landscape of Matrix and Tensor Decomposition Problems
Tengyu Ma, Princeton University
7.
The State of Contemporary Computing Substrates for Optimization Methods
Ben Recht, UC Berkeley
8.
Let's Make Block Coordinate Descent Go Fast
Mark Schmidt, University of British Columbia
9.
Stochastic, Second-order Black-box Optimization for Step Functions
Katya Scheinberg, Lehigh University
10.
Algorithmic Tools for Smooth Nonconvex Optimization
Steve Wright, University of Wisconsin-Madison
11.
Zero-order and Dynamic Sampling Methods for Nonlinear Optimization
Jorge Nocedal, Northwestern University
12.
Dealing with Linear Constraints via Random Permutation
Ruoyu Sun, University of Illinois at Urbana-Champaign
13.
Randomized Iterative Methods and Complexity for Markov Decision Process
Mengdi Wang, Princeton University
14.
Sketching as a Tool for Fast Algorithm Design
Alex Andoni, Columbia University
15.
Sublinear Time Low-rank Approximation of Positive Semidefinite Matrices
David Woodruff, IBM Almaden
16.
Hashing-based-estimators for Kernel Density in High Dimensions
Moses Charikar, Stanford University
17.
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
Madeleine Udell, Cornell University
18.
Trends in Large-scale Nonconvex Optimization
Suvrit Sra, MIT
19.
Faster Algorithms and New Iterative Methods for Computing the Stationary Distribution
Aaron Sidford, Stanford University
20.
Nonconvex Optimization for High-dimensional Learning: From ReLUs to Submodular Maximization
Mahdi Soltanolkotabi, University of Southern California
21.
Will Vanishing Gradients Ever Vanish from Deep Learning?
Moritz Hardt, UC Berkeley
22.
From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
Alina Ene, Boston University
23.
Natasha 2: Faster Non-convex Optimization Than SGD
Zeyuan Allen-Zhu, Microsoft Research
Discrete Optimization via Continuous Relaxation
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
1.
The Power of Hierarchies for Detecting Hidden Structures
Prasad Raghavendra, UC Berkeley
2.
Simplex Transformations and Multiway Cut
Roy Schwartz, Technion - Israel Institute of Technology
3.
LPs and Convex Programming Relaxations and Rounding for Stochastic Problems
Anupam Gupta, Carnegie Mellon University
4.
Discrepancy and Approximation Algorithms
Sasho Nikolov, University of Toronto
5.
On Approximating the Covering Radius and Finding Dense Lattice Subspaces
Daniel Dadush, Centrum Wiskunde & Informatica
6.
A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming
Rico Zenklusen, ETH Zürich
7.
Improved Approximation Algorithms for the TSP and S-t-path TSP
David Shmoys, Cornell University
8.
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
László Végh, London School of Economics
9.
Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing
Chaitanya Swamy, University of Waterloo
10.
Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation...
Fabrizio Grandoni, IDSIA, University of Lugano
11.
Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations
Shi Li, SUNY Buffalo
12.
LP Rounding for Poise
R. Ravi, Carnegie Mellon University
13.
Submodular Optimization
Niv Buchbinder, Tel Aviv University
14.
Submodular Unsplittable Flow on Trees
Anna Adamaszek, University of Copenhagen
15.
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Alina Ene, Boston University
16.
Online Optimization, Smoothing, and Competitive Ratio
Maryam Fazel, University of Washington
17.
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Dartmouth College
18.
Beyond Worst Case Analysis in Approximation
Uri Feige, Weizmann Institute of Science
19.
Algorithms for Stable and Perturbation-resilient Problems
Kostya Makarychev, Northwestern University
20.
Scheduling on Related Machines
Debmalya Panigrahi, Duke University
21.
Low Diameter Graph Decompositions and Approximating Unique Games
Lap-Chi Lau, University of Waterloo
22.
A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
Thomas Rothvoß, University of Washington
23.
LP Relaxations for Reordering Buffer Management
Yuval Rabani, The Hebrew University of Jerusalem
24.
A Survey of Dependent Rounding
Aravind Srinivasan, University of Maryland
25.
Finding Best LP Relaxations for Various Cut Problems
Euiwoong Lee, Carnegie Mellon University
26.
Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne
27.
Approximating the Permanent of Positive Semidefinite Matrices
Nima Anari, Stanford University
28.
Local Guarantees in Graph Cuts and Clustering
Moses Charikar, Stanford University
Interior Point Methods 4
Aug. 2017
Steve Wright, University of Wisconsin-Madison; Aaron Sidford, Stanford University; and Aleksander Mądry, MIT
https://simons.berkeley.edu/talks/interior-point-methods-4
Bridging Continuous and Discrete Optimization Boot Camp
Geometry, Optimization and Generalization in Multilayer Networks
Mar. 2017
Nathan Srebro, TTI Chicago
Representation Learning
https://simons.berkeley.edu/talks/nathan-srebro-bartom-2017-3-27
Representation Learning
This workshop will focus on dramatic advances in representation and learning taking place in natural language processing, speech and vision. For instance, deep learning can be thought of as a method that combines the tasks of finding a classifier (which we can think of as the top layer of the deep net) with the task of learning a representation (namely, the representation computed at the last-but-one layer).
Playlist: 30 videos
1.
Geometry, Optimization and Generalization in Multilayer Networks
Nathan Srebro, TTI Chicago
2.
A Non-generative Framework and Convex Relaxations for Unsupervised Learning
Elad Hazan, Princeton University
3.
Representations for Language: From Word Embeddings to Sentence Meanings
Christopher Manning, Stanford University
4.
The Missing Signal
Leon Bottou, Facebook AI Research
5.
Representations of Relationships in Images and Text
Hal Daume, University of Maryland at College Park
6.
Spotlight Talk: A Formalization of Representation Learning
Andrej Risteski, Princeton University
7.
Spotlight Talk: Semi-Random Units for Learning Neural Networks with Guarantees
Bo Xie, Georgia Institute of Technology
8.
Unsupervised Discovery Through Adversarial Self-Play
Rob Fergus, New York University
9.
Learning from Unlabeled Video
Kristen Grauman, University of Texas, Austin
10.
Deep Reinforcement Learning
Pieter Abbeel, UC Berkeley
11.
Supersizing Self-Supervision: Learning Perception and Action without Human Supervision
Abhinav Gupta, Carnegie Mellon University
12.
Failures of Deep Learning
Shai Shalev-Shwartz, Hebrew University of Jerusalem
13.
Continuous State Machines and Grammars for Linguistic Structure Prediction
Noah Smith, University of Washington
14.
Adversarial Perceptual Representation Learning Across Diverse Modalities and Domains
Trevor Darrell, UC Berkeley
15.
Evaluating Neural Network Representations Against Human Cognition
Tom Griffiths, UC Berkeley
16.
Representation Learning for Reading Comprehension
Russ Salakhutdinov, Carnegie Mellon University
17.
Tractable Learning in Structured Probability Spaces
Adnan Darwiche, UCLA
18.
Spotlight Talk: Convolutional Dictionary Learning through Tensor Factorization
Furong Huang, UC Irvine
19.
Spotlight Talk: How to Escape Saddle Points Efficiently
Praneeth Netrapalli, Microsoft Research India
20.
Re-Thinking Representational Learning in Robotics and Music
Sham Kakade, University of Washington
21.
Representation Learning of Grounded Language and Knowledge: with and without End-to-End Learning
Yejin Choi, University of Washington
22.
Unsupervised Representation Learning
Yann LeCun, New York University
23.
Generalization and Equilibrium in Generative Adversarial Nets (GANs)
Sanjeev Arora, Princeton University
24.
Provably Learning of Noisy-or Networks
Rong Ge, Duke University
25.
Learning Paraphrastic Representations of Natural Language Sentences
Kevin Gimpel, TTI Chicago
26.
Formation and Association of Symbolic Memories in the Brain
Christos Papadimitriou, UC Berkeley
27.
Learning Representations for Active Vision
Bruno Olshausen, UC Berkeley
28.
Resilient Representation and Provable Generalization
Dawn Song, UC Berkeley
29.
Word Representation Learning without unk Assumptions
Chris Dyer, Carnegie Mellon University
30.
Spotlght Talk: Performance Guarantees for Transferring Representations
Daniel McNamara, Australian National University
From Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
Sep. 2016
Yaron Singer, Harvard University
https://simons.berkeley.edu/talks/yaron-singer-09-20-2016
Optimization and Decision-Making Under Uncertainty
Using Molecular Networks to Seed Predictive Hierarchies of Cell Systems
Apr. 2016
Trey Ideker, UC San Diego
Network Biology
https://simons.berkeley.edu/talks/trey-ideker-04-11-16
Workshop on Neo-Classical Methods in Discrete Analysis
Dec. 2 – Dec. 6, 2013
Playlist: 23 videos
1.
Threshold, Influence, Noise, and Discrete Harmonic Analysis
Gil Kalai, Hebrew University of Jerusalem
2.
Structure of the Fourier Spectrum of Boolean Functions and Complexity
Ben Lee Volk, Technion Israel Institute of Technology
3.
Quantitative Aspects of the Idempotent Theorem
Tom Sanders, University of Oxford
4.
Families of Permutations with Forbidden Intersection-sizes
David Ellis, Weizmann Institute of Science and Queen Mary, University of London
5.
Friedgut-Kalai-Naor for Boolean Functions on S_n
Yuval Filmus, University of Toronto
6.
A Short Proof of Gowers' Lower Bound for the Regularity Lemma
Asaf Shapira, Tel Aviv University
7.
Carries and Cocycles
Persi Diaconis, Stanford University
8.
The Green-Tao Theorem and a Relative Szemeredi Theorem
Yufei Zhao, Massachusetts Institute of Technology
9.
Algorithmic Regularity for Polynomials and Applications
Arnab Bhattacharyya, Indian Institute of Science
10.
Ultraproducts as a Bridge Between Discrete and Continuous Analysis
Terry Tao, UCLA
11.
Undecidability of Linear Inequalities Between Graph Homomorphism Densities
Hamed Hatami, McGill University
12.
Non-commutative Computation
Avi Wigderson, Institute for Advanced Study, Princeton
13.
Small Lifts of Expander Graphs are Expanding
Alexandra Kolla, University of Illinois, Urbana-Champaign
14.
Building Monotone Expanders
Amir Yehudayoff, Technion Israel Institute of Technology
15.
The Structure of Low Rank Matrices
Shachar Lovett, UC San Diego
16.
Counting Sumsets and Applications
Ben Green, University of Oxford
17.
Incidence Geometry and Applications to Theoretical Computer Science
Shubhangi Saraf, Rutgers University
18.
Laplacian Eigenvalues, Metric Uniformization, and Incidence Geometry
James Lee, University of Washington
19.
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Justin Thaler, Harvard University
20.
Vertical Versus Horizontal Poincare Inequalities
Assaf Naor, Courant Institute, NYU
21.
Partial Difference Equations Over Compact Abelian Groups
Tim Austin, Courant Institute, NYU
22.
Some Pseudorandom Phenomena in Finite Fields
Swastik Kopparty, Rutgers University
23.
Discrete Tori and Bounds for Linear Codes
Alex Samorodnitsky, Hebrew University of Jerusalem