Playlist: 20 videos

Connections Between Algorithm Design and Complexity Theory

Sept. 28 – Oct. 1, 2015

Much significant work on lower bounds in complexity theory has arisen from reconsidering the basic lower bound problem in an algorithmic light. Namely, if computations on small circuits can be performed somewhat efficiently...

0:55:17

Human Computation

Manuel Blum, Carnegie Mellon University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/manuel-blum-2015-09-28
Visit talk page
0:45:14

Explicit Two-Source Extractors and Resilient Functions

David Zuckerman, University of Texas, Austin
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/david-zuckerman-2015-09-28
Visit talk page
0:45:44

On the Power of Gradually Increasing Independence

Parikshit Gopalan, Microsoft Research
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/parikshit-gopalan-2015-09-28
Visit talk page
0:17:4

Anti-Concentration for Polynomials of Independent Random Variables

Raghu Meka, UCLA
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/raghu-meka-2015-09-28
Visit talk page
0:17:26

Lower Bounds by Birkhoff Interpolation

Pascal Koiran, École Normale Supérieure de Lyon
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/pascal-koiran-2015-09-28
Visit talk page
0:10:59

Sublinear Space Complexity

Osamu Watanabe, Tokyo Institute of Technology
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/osamu-watanabe-2015-09-28
Visit talk page
0:57:18

Chasing Lower Bounds

Avi Widgerson, Institute for Advanced Study, Princeton
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/avi-wigderson-2015-09-29
Visit talk page
0:43:28

Local Reductions

Emanuele Viola, Northeastern University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/emanuele-viola-2015-09-29
Visit talk page
0:17:31

Getting Harder All the Time?

Omer Reingold, Samsung Research America
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/omer-reingold-2015-09-29
Visit talk page
0:17:2

Derandomization via Robust Algebraic Circuit Lower Bounds

Michael Forbes, Princeton University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/michael-forbes-2015-09-29
Visit talk page