![Satisfiability_hi-res-logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Satisfiability_hi-res.jpg?h=b86da943&itok=JIajwKvC)
Abstract
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.