$\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 the BMS Friday Colloquium by Prof. Avi Wigderson
Urania Berlin, at the 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.