Circuit Lower Bounds (and More) via the Fusion Method

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


Duration: 1:05:04
947 views
7

Avi Wigderson (IAS)
https://simons.berkeley.edu/talks/tbd-9
Boolean Devices



Other Videos By Simons Institute for the Theory of Computing


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
2018-09-11Lifting Nullstellensatz Degree to Monotone Span Program Size
2018-09-10Static Data Structure Lower Bounds Imply Rigidity
2018-09-10Lower Bounds for Unrestricted Boolean Circuits: Open Problems
2018-09-10Oracle Separation of BQP and the Polynomial Hierarchy
2018-09-10Pseudorandom Generators from Polarizing Random Walks
2018-09-10The KRW Conjecture: Results and Open Problems
2018-09-10Circuit Lower Bounds (and More) via the Fusion Method
2018-09-07Networking Theory: A Personal Perspective
2018-09-07Emerging Trends & Applications in Communication Networks
2018-09-07The Future of Wireless and What It Will Enable
2018-09-07The Future Quantum Internet: Challenges
2018-09-07Interference Queuing Networks
2018-09-07A Surge-type Pricing in Ridesharing Systems is Stability Optimal
2018-09-07Excursions of Max-weight Dynamics
2018-09-07Incentive Compatibility in Stochastic Dynamic Systems
2018-09-07Opening Remarks
2018-09-06Through Two Doors at Once


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Boolean Devices
Avi Wigderson