Lower Bounds by Birkhoff Interpolation

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


Duration: 17:26
541 views
4

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



Other Videos By Simons Institute for the Theory of Computing


2015-10-19The Query Complexity of Correlated Equilibria
2015-10-19Econometrics for Learning Agents
2015-10-19Robustness and Separation in Multidimensional Mechanism Design
2015-10-19First Price Auctions with General Information Structures: Implications for Bidding and Revenue
2015-10-19Revenue Maximization in Interdependent Value Settings
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-01Lower Bounds by Birkhoff Interpolation
2015-10-01On the Existence of Optimal Algorithms
2015-10-01Probabilistic Polynomials and Hamming Nearest Neighbors
2015-10-01Derandomization via Robust Algebraic Circuit Lower Bounds
2015-10-01Chasing Lower Bounds
2015-10-01Anti-Concentration for Polynomials of Independent Random Variables
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


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