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 WorkshopNew Directions in Proof ComplexityApproximate counting in bounded arithmeticAuthor: E Jerabek (University of Toronto) 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. |