• Pavel Hubá?ek
    • (MFF UK)
    • The Journey from NP to TFNP Hardness
    • Abstract:
    • 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.
    • 08.06.18   13:30
    • Diptarka Chakraborty
    • (Charles University)
    • Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
    • Abstract:
    • 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$ satisfying $t r = \tilde{\Omega}(n^3)$. For $r \leq n$, any data structure must have $t = \tilde{\Omega}(n^2)$. Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. This talk will be based on a joint work with Lior Kamma and Kasper Green Larsen (to appear in STOC'18).
    • 25.05.18   13:30

    Michal Koucky, Pavel Pudlak