An Isaac Newton Institute Workshop

New Directions in Proof Complexity

Approximate counting in bounded arithmetic

Author: E Jerabek (University of Toronto)


We use the dual weak pigeonhole principle to develop approximate counting in bounded arithmetic. As an application, we show how to formalize classes of randomized algorithms, such as BPP.