### Abstract

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.

## An Isaac Newton Institute Workshop## New Directions in Proof Complexity## Approximate counting in bounded arithmetic
## AbstractWe 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. |