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:17:26

Graph Automorphism and Circuit Size

Eric Allender, Rutgers University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/eric-allender-2015-09-29
Visit talk page
0:49:46

On the Existence of Optimal Algorithms

Boaz Barak, Microsoft Research and Harvard University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/boaz-barak-2015-09-30
Visit talk page
0:48:59

A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials

Srikanth Srinivasan, Indian Institute of Technology Bombay
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/srikanth-srinivasan-2015-09-30
Visit talk page
0:53:56

Approaches to Bounding the Exponent of Matrix Multiplication

Chris Umans, California Institute of Technology
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/chris-umans-2015-09-30
Visit talk page
0:46:5

QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds

Rahul Santhanam, University of Edinburgh
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/rahul-santhanam-2015-10-1
Visit talk page
0:41:44

Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates

Suguru Tamaki, Kyoto University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/suguru-tamaki-2015-10-01
Visit talk page
0:35:16

Probabilistic Polynomials and Hamming Nearest Neighbors

Joshua Alman, Stanford University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/joshua-alman-2015-10-01
Visit talk page
0:18:24

Generalizations of the Gate Elimination Method

Alexander Kulikov, St. Petersburg Department of Steklov Institute of Mathematics
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/alexander-kulikov-2015-10-01
Visit talk page
0:15:16

Addition is Exponentially Harder than Counting for Shallow Monotone Circuits

Igor Oliveira, Columbia University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/igor-oliveira-2015-10-01
Visit talk page
0:16:30

Satisfiability Algorithms Based on Concentrated Shrinkage

Ruiwen Chen, University of Edinburgh
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/ruiwen-chen-2015-10-01
Visit talk page