Extension-Based Proofs

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


Duration: 26:10
436 views
3

Faith Ellen (University of Toronto)
https://simons.berkeley.edu/talks/faith-ellen-2023-03-27
ToniCS: Celebrating the Contributions and Influence of Toniann Pitassi

A valency argument is an elegant and well-known technique for proving impossibility results in distributed computing. It is an example of an extension-based proof, which is modelled as an interaction between a prover and a protocol. We will discuss some impossibility results in distributed computing that cannot be proved using extension-based proofs. This work was inspired by Toni's early work on weak proof systems that cannot be used to prove the pigeonhole principle.



Other Videos By Simons Institute for the Theory of Computing


2023-03-29Efficient Quantum Gibbs Samplers | Quantum Colloquium
2023-03-29My Collaborations with Toni Pitassi
2023-03-29Open Problems that Baffled Toni (so far)
2023-03-29Working with Toni in Algebraic Proof Complexity
2023-03-28On Extended Frege Proofs
2023-03-28Efficient Quantum Gibbs Samplers | Quantum Colloquium
2023-03-28Student Session - talks from Denis Pankratov, David Madras, Ian Mertz, Yuval Filmus
2023-03-28How to Solve Math Problems Without Talent
2023-03-28Student Session
2023-03-28Theory and Practice: Some Things I Learned About Computation and Life From Toni Pitassi
2023-03-28Extension-Based Proofs
2023-03-28Toni Counts, Continually!
2023-03-27In Search of the Ideal: Toni Pitassi and her work on Algebraic Proof Systems
2023-03-25TFNP
2023-03-25Lower Bounds for NW-generators in AC0-Frege
2023-03-25Implicit Proof Systems
2023-03-24Unprovability and Other Impossibility Results in Machine Learning
2023-03-24Weak Versions of Extended Resolution
2023-03-24CDCL vs Resolution: The Picture in QBF
2023-03-24Read-Once Branching Programs as Proof Lines
2023-03-24Connections Between QBF Proof Complexity and Circuit Complexity


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
ToniCS: Celebrating the Contributions and Influence of Toniann Pitassi
Faith Ellen