Circuit Lower Bounds from Algorithm Design: An Overview I (Partial)

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


Duration: 52:42
1,824 views
21

Ryan Williams, MIT
https://simons.berkeley.edu/talks/lower-bounds-algorithm-design-i
Lower Bounds in Computational Complexity Boot Camp



Other Videos By Simons Institute for the Theory of Computing


2018-08-22Lower Bounds in Arithmetic Circuit Complexity I
2018-08-22Geometric Complexity Theory II: Complexity Lower Bounds...
2018-08-22Geometric Complexity Theory I: Complexity Lower Bounds...
2018-08-21Derandomization from Circuit Lower Bounds II
2018-08-21Derandomization from Circuit Lower Bounds I
2018-08-21Lower Bounds Techniques in Proof Complexity II
2018-08-21Lower Bounds Techniques in Proof Complexity I
2018-08-20Restriction-based Methods II
2018-08-20Restriction-based Methods I
2018-08-20Circuit Lower Bounds from Algorithm Design: An Overview II
2018-08-20Circuit Lower Bounds from Algorithm Design: An Overview I (Partial)
2018-07-25TUTORIAL: Recent Development in Selective Inference II
2018-07-25TUTORIAL: Recent Development in Selective Inference I
2018-07-24TUTORIAL: Recent Development in Differential Privacy II
2018-07-24TUTORIAL: Recent Development in Differential Privacy I
2018-07-18Mind Over Data: The One Thing You Know and Machines Don't
2018-06-15Spatial Isolation Implies Zero Knowledge Even in a Quantum World
2018-06-15Non-Interactive Verifiable Computation via Non-signaling
2018-06-15Verifying Quantum Proofs with Entangled Games
2018-06-15Classical Verification of Quantum Computations
2018-06-15Cryptography for Quantum Computers


Tags:
Lower Bounds in Computational Complexity Boot Camp
Ryan Williams
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley