Connections Between Algorithm Design and Complexity Theory

# click the upper-left icon to select videos from the playlist

source: Simons Institute      2015年10月1日
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, then this strongly suggests limitations on what tasks can be done with small circuits. Formalizing this intuition has led to generic connections between nontrivial algorithms which perform interesting computations on given circuit classes, and nontrivial complexity limitations on the same circuit classes. This workshop aims to bring many algorithm designers and complexity theorists together to discuss the developments in their respective areas and to reconsider these connections broadly.
For more information, please visit https://simons.berkeley.edu/workshops/complexity2015-1.
These presentations were supported in part by an award from the Simons Foundation.

Human Computation Manuel Blum, Carnegie Mellon University https://simons.berkeley.edu/talks/man...   55:17
Explicit Two-Source Extractors and Resilient Functions 45:15
On the Power of Gradually Increasing Independence 45:44
Anti-Concentration for Polynomials of Independent Random Variables 17:04
Lower Bounds by Birkhoff Interpolation 17:26
Sublinear Space Complexity 10:59
Chasing Lower Bounds 57:18
Local Reductions 43:28
Getting Harder All the Time? 17:31
Derandomization via Robust Algebraic Circuit Lower Bounds 17:02
Graph Automorphism and Circuit Size 17:27
On the Existence of Optimal Algorithms 49:46
A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials 48:59
Approaches to Bounding the Exponent of Matrix Multiplication 53:56
QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds 46:05
Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates 41:44
Probabilistic Polynomials and Hamming Nearest Neighbors 35:16
Generalizations of the Gate Elimination Method 18:24
Addition is Exponentially Harder than Counting for Shallow Monotone Circuits 15:16
Satisfiability Algorithms Based on Concentrated Shrinkage 16:30