### Approximate counting in bounded arithmetic

Jerabek, E *(Toronto)*

Monday 10 April 2006, 15:30-16:00

Seminar Room 1, Newton Institute

#### 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.

#### Presentation