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.

The Journey from NP to TFNP Hardness

Pavel Hubáček
Friday, 8. June 2018 - 13:30 to 15:00

in IM, rear building, ground floor

The complexity class TFNP is the search analogue of the class NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. In my talk, I will show that hard-on-average TFNP problems exist under the weak assumption that there exists a hard-on-average language in NP. In terms of techniques, our results demonstrate an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs. Based on joint work with Moni Naor and Eylon Yogev.

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication

Diptarka Chakraborty
Charles University
Friday, 25. May 2018 - 13:30 to 15:00

in IM, rear building, ground floor

The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure (that is, we only charge for memory accesses, while computation is free). Their cell probe data structure answers queries in $\tilde{O}(n^{7/4})$ time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional $\tilde{O}(n^{7/4})$ bits on the side. In this talk, we present a new cell probe data structure with query time $\tilde{O}(n^{3/2})$ storing just $\tilde{O}(n^{3/2})$ bits on the side. We then complement our data structure with a matching lower bound showing that any data structure storing $r$ bits on the side, with $n < r < n^2$ must have query time $t$... more

Matroids, 3-regular graphs and random restrictions

Pavel Pudlák
Friday, 11. May 2018 - 13:30 to 15:00

in IM, rear building, ground floor

I will show some connections between matroids and random restrictions of Tseitin tautologies on 3-regular graphs. In particular I will show that the domains of the restrictions are flats in a matroid that is dual to a bicircular matroid. I will pose several problems concerning how these facts can be generalized to other kinds of restrictions and other graphs. This talk will be a sort of a continuation of Navid's, but I will recall everything that is needed.

Half-duplex communication complexity

Alexander V. Smal
Steklov Math. Inst., St. Petersburg
Friday, 4. May 2018 - 13:30 to 15:00

in IM, rear building, ground floor

Suppose Alice and Bob are communicating bits to each other in order to compute some function f but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is in fact more powerful than the classical one as it allows to compute some functions in smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions. Join... more