Natural Properties, MCSP, and Proving Circuit Lower Bounds

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


Duration: 35:40
419 views
7

Valentine Kabanets (Simon Fraser University)
https://simons.berkeley.edu/talks/minimum-circuit-size-problem-recent-results-and-future-directions
Boolean Devices



Other Videos By Simons Institute for the Theory of Computing


2018-09-14A Short List of Equalities Has Large Sign Rank
2018-09-14The Coin Problem and AC^0[parity]
2018-09-14Does Looking Inside a Circuit Help?
2018-09-14The Complexity of Distributions
2018-09-14Distribution-Free Junta Testing
2018-09-14The Pathset Approach to Formula Lower Bounds
2018-09-13Boolean Matrix Multiplication Lower Bounds
2018-09-13New Lower Bounds Through an Improved Easy Witness Lemma
2018-09-13Recent Structure Lemmas for Depth-two Threshold Circuits
2018-09-13A Review of Some Recent Lower Bounds Against Low-Depth Threshold Circuits
2018-09-13Natural Properties, MCSP, and Proving Circuit Lower Bounds
2018-09-13Hardness Magnification
2018-09-13A Survey on MCSP
2018-09-12Clique Is Hard on Average for Regular Resolution
2018-09-12Fooling Polytopes
2018-09-12An Overview of Quantified Derandomization
2018-09-11Locating Linear Decision Lists within TC^0
2018-09-11Monotone Circuit Lower Bounds from Resolution (Now with Applications!)
2018-09-11BPP Lifting and Its Applications
2018-09-11Approximate Degree and Quantum Query Lower Bounds via Dual Polynomials
2018-09-11Algorithmic Polynomials


Tags:
Boolean Devices
Valentine Kabanets
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley