The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

LAA

Seminar

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

[pdf ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧