skip to content

Approximate counting in bounded arithmetic

Presented by: 
E Jerabek [Toronto]
Monday 10th April 2006 - 15:30 to 16:00
INI Seminar Room 1

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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons