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.

A separator theorem for hypergraphs and a CSP-SAT algorithm
Navid Talebanfard
IM
Friday, 12. April 2019 - 13:30 to 15:00

in IM, rear building, ground floor

I'll show how to remove a small number of edges from a uniform hypergraph of small vertex degree to break it
into small connected components. I'll use it to give a CSP-SAT algorithm for CSPs with small variable frequency.

This is joint work with Vojtěch Rödl.

Attribute-Based Encryption and Information-Theoretic Crypto
Hoeteck Wee
CNRS and ENS
Friday, 29. March 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Can we encrypt data while enabling fine-grained access control, as is necessary to protect big, complex data? In this talk, we will survey how addressing this question led to new lower and upper bounds in information-theoretic cryptography and secret sharing, which in turn came from building new connections to communication complexity and private information-retrieval.

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.

 

Pages