Full name: Ondřej Ježil
Affiliation: Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Title of the talk: Primes, feasible computation and reasoning
Abstract: In 2002, the first primality test which runs in deterministic polynomial time was discovered -- the AKS algorithm. In other words: the primality of a number is a feasible property. Can we prove this by only manipulating other feasible properties? In this talk, we will discuss our recent attempts at proving the correctness of the AKS algorithm in the weakest possible theory of bounded arithmetic. This talk is based on joint work with Raheleh Jalali.