slideshow 3

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.  
 

Pages