$\vec{w}h\alpha\mathfrak{t}\;\; \forall\mathbb{R}\varepsilon\ldots$

BPP, RP and the other probabilistic complexity classes?

Josué Tonelli Cueto (TU Berlin)
2017/06/30, 13:00
Before BMS Friday Colloquium by Prof. Avi Wigderson
Urania Berlin, at BMS Loft (3rd floor)
About what?

When one faces problems to solve, randomness can be used in order obtain faster answers at the cost of some uncertainty. Probabilistic complexity classes capture the different ways in which this can be done. In this talk, we introduce the basic probabilistic complexity classes, their interrelations and we illustrate by outlining the solution to concrete problems.