# Complexity seminar

usually takes place each Friday at 13:30 in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

### Circuit lower bounds via non-negative rank

##### Pavel Hrubeš
IM CAS
Friday, 15. March 2019 - 13:30 to 15:00

in IM, rear building, ground floor

The non-negative rank of a matrix is a quantity which has found several applications in communication
complexity and extension complexity of polytopes. We will show that certain lower bounds on non-negative rank
imply, at least in principle, circuit lower bounds. With a Boolean function $f$ and $\epsilon>0$, we associate
an explicit matrix $M_\epsilon(f)$ so that the circuit size of $f$ is at least the non-negative rank of
$M_{\epsilon}(f)$, for $\epsilon$ sufficiently small. We also discuss continuity properties of the
non-negative rank.

### Stronger Lower Bounds for Online ORAM

##### Veronika Slivova
MFF UK
Friday, 1. March 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Oblivious RAM (ORAM), introduced in the context of software protection
by Goldreich and Ostrovsky [JACM’96], aims at obfuscating the memory
access pattern induced by a RAM computation. We will show that every
implementation of Online Oblivious RAM has logarthmic overhead.

Joint work with P. Hubacek, M. Koucky and K. Kral.

### 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.