slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Deterministic indeterminacy of CHSH-solving protocols
Dmitri Gavinsky
IM
Friday, 15. February 2019 - 13:30 to 15:00

in IM, rear building, ground floor

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.

How to compute random Boolean function over the reals.
Pavel Hrubeš
IM
Friday, 1. February 2019 - 13:30 to 15:00

in IM, rear building, ground floor

We consider the problem of defining a Boolean function by means of a first-order 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.  
 

Entropy extractors for small zero-fixing sources, part III
Pavel Pudlák
IM
Friday, 25. January 2019 - 13:30 to 15:00

in IM, rear building, ground floor

I will finish the first construction by presenting the skeleton-fixing procedure and start the second construction.

Entropy extractors for small zero fixing sources, part II
Pavel Pudlák
IM
Friday, 18. January 2019 - 13:30 to 15:00

in IM, rear building, ground floor
 

I will continue with the construction of an extractor for zero fixing sources of triple logarithmic size.
 

Pages