
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 hardonaverage TFNP problems exist under the weak assumption that there exists
a hardonaverage language in NP. In terms of techniques, our results demonstrate an interesting interplay
between problems in TFNP, derandomization techniques, and zeroknowledge proofs.
Based on joint work with Moni Naor and Eylon Yogev.

Diptarka Chakraborty
 (Charles University)

Tight Cell Probe Bounds for Succinct Boolean MatrixVector Multiplication

Abstract:

The conjectured hardness of Boolean matrixvector 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 readonly 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 wordRAM 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).
Michal Koucky, Pavel Pudlak
organizers