
Dmitri Gavinsky
 (IM)

Deterministic indeterminacy of CHSHsolving protocols

Abstract:

How unpredicatble is the behaviour of efficient entagled players in the CHSH game?
We will discuss this question from both qualitative and quantitative point viewpoints.

Pavel Hrubeš
 (IM)

How to compute random Boolean function over the reals.

Abstract:

We consider the problem of defining a Boolean function by means of a firstorder formula over the reals. We discuss the connection of this problem with other questions in computational complexity. We also outline some bounds on the size of formulas computing a random Boolean function.
Michal Koucky, Pavel Pudlak
organizers