On the Existence of Optimal Algorithms

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=9_35z4z2X6w


Duration: 49:46
1,177 views
18

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



Other Videos By Simons Institute for the Theory of Computing


2015-10-19Competition and Simple Auctions
2015-10-08Thinking Algorithmically About Impossibility
2015-10-01Satisfiability Algorithms Based on Concentrated Shrinkage
2015-10-01Generalizations of the Gate Elimination Method
2015-10-01Addition is Exponentially Harder than Counting for Shallow Monotone Circuits
2015-10-01Graph Automorphism and Circuit Size
2015-10-01On the Power of Gradually Increasing Independence
2015-10-01Local Reductions
2015-10-01Explicit Two-Source Extractors and Resilient Functions
2015-10-01Lower Bounds by Birkhoff Interpolation
2015-10-01On the Existence of Optimal Algorithms
2015-10-01Getting Harder All the Time?
2015-10-01QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds
2015-10-01A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials
2015-10-01Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates
2015-10-01Sublinear Space Complexity
2015-10-01Human Computation
2015-10-01Approaches to Bounding the Exponent of Matrix Multiplication
2015-09-18Learning and Efficiency in Games
2015-09-09Proof of NEXP Not in ACC
2015-09-09Computational Complexity of Polynomial Time Problems: Introduction


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Fine-Grained Complexity and Algorithm Design
Boaz Barak