Proof Complexity and TFNP

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


Duration: 16:10
287 views
1

Robert Robere (McGill University)
https://simons.berkeley.edu/talks/proof-complexity-tfnp
Meet the Fellows Welcome Event Spring 2023



Other Videos By Simons Institute for the Theory of Computing


2023-02-14How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
2023-02-14Journey with Eric Allender: From Turing Machines to Circuits, and Back
2023-02-14Improved Learning from Time-bounded Kolmogorov Complexity
2023-02-14NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
2023-02-14Allender's Conjecture and its Impacts on Meta-Complexity
2023-02-13A Commentary on the Collision of Worlds
2023-02-09How Complex Is Complexity? Or What’s a ‘Meta’ for?
2023-02-02The Power of Randomness in Kolmogorov Complexity
2023-01-28Emulating Non-Local Games with Cryptography
2023-01-28Is Cryptography Feasible if P=NP?
2023-01-28Proof Complexity and TFNP
2023-01-28Learning versus Proofs of Complexity Lower Boundes
2023-01-27Understanding the Role of Derandomization in TCS
2023-01-27New Forms of Hardness versus Randomness
2023-01-27Quantum for Science
2023-01-27Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
2023-01-27The Power of Randomness in Kolmogorov Complexity
2023-01-21Automatability: The Proof Search Problem
2023-01-21Proofs, Circuits and Total Search Problems
2023-01-21Proof Complexity and Meta-Complexity Tutorial (2)
2023-01-20Proof Complexity and Meta-Complexity Tutorial (1)


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Spring 2023
Robert Robere