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.

Adaptively-secure secret sharing

Chethan Kamath
IST Austria
Friday, 20. October 2017 - 13:30 to 15:00

in IM, rear building, ground floor

A secret-sharing scheme is used to distribute a secret between a set of participants so that a subset of the participants that satisfy certain conditions can reconstruct the secret. In the computational setting, it is relatively easy to achieve selective security (where the adversary commits a-priori to the set of corrupt participants), but appears difficult to achieve the more natural notion of adaptive security (where the adversary can corrupt participants as the attack progresses). It is well known that selective security, where the adversary has to commit to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2^n. In this talk we will see how one can, in certain cases, achieve better bounds than 2^n by using techniques from graph pebbling.  (Based on joint work with Zahra Jafargholi, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, and Daniel Wichs.)

Quantum versus classical simultaneity in communication complexity

Dmitri Gavinsky
Friday, 2. June 2017 - 13:30 to 15:00

in IM, rear building, ground floor

We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message passing – even without shared randomness. This can be interpreted as the strongest known − as of today − example of "super-classical" capabilities of the weakest studied model of quantum communication.

Testing Equality in Communication Graphs

Klim Efremenko
Tel-Aviv University
Friday, 19. May 2017 - 13:30 to 15:00

in IM, rear building, ground floor

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose that on each vertex of the graph there is a player having an $n$-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem? We determine this minimum up to a lower order additive term in many cases (but not for all graphs).   In particular, we show that it is $kn/2+o(n)$ for any Hamiltonian $k$-vertex graph, and that for any $2$-edge connected  graph with $m$ edges containing no two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$. The proofs combine graph theoretic ideas with tools from additive number theory.

Cluster Planarity

Filip Šedivý
Faculty of Mathematics and Physics, Charles Univ.
Friday, 7. April 2017 - 13:30 to 15:00

in IM, rear building, ground floor

This thesis studies the problem of clustered planarity and follows two directions. First direction deals with computational complexity, where we show how clustered planarity can be solved in linear nondeterministic time in terms of the number of vertices of the input graph. Second directions is characterization of restricted versions of clustered planarity using minimal non-clustered-planar instances. For this purpose we introduce a notion of clustered minor using several operations reducing clustered graphs. We show that these operations preserve clustered planarity. We show that in the case of clustered graphs where clusters have size 2 and the graph is a cycle or a path, there are only finitely many minimal non-clustered-planar minors. We also mention known results about the computational complexity of clustered planarity.