1st workshop of the Center for Foundations of Modern Computer Science
1. workshop Centra základů moderní informatiky
The first workshop of the Center for Foundations of Modern Computer Science will take place on Tuesday July 21, 2018, in the Mala Strana building. It is a part of the Midsummer Combinatorial Workshop XXIII.
| 9:00 | Jan Kynčl: The $Z_2$-genus of Kuratowski minors |
|---|---|
| 9:30 | Andreas E. Feldmann: The Parameterized Hardness of the k-Center Problem in Transportation Networks |
| 10:00 | Pavel Hubáček: On Constant-Round Statistical Zero-Knowledge |
Abstracts
Jan Kynčl: The $Z_2$-genus of Kuratowski minors
A drawing of a graph on a surface is \emph{independently even} if every pair of nonadjacent edges in the drawing crosses an even number of times. The \emph{$\mathbb{Z}_2$-genus} of a graph $G$ is the minimum $g$ such that $G$ has an independently even drawing on the orientable surface of genus $g$. An unpublished result by Robertson and Seymour implies that for every $t$, every graph of sufficiently large genus contains as a minor a projective $t\times t$ grid or one of the following so-called \emph{$t$-Kuratowski graphs}: $K_{3,t}$, or $t$ copies of $K_5$ or $K_{3,3}$ sharing at most $2$ common vertices. We show that the $\mathbb{Z}_2$-genus of graphs in these families is unbounded in $t$; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its $\mathbb{Z}_2$-genus, solving a problem posed by Schaefer and \v{S}tefankovi\v{c}, and giving an approximate version of the Hanani--Tutte theorem on orientable surfaces. These results were obtained together with Radoslav Fulek.
Andreas E. Feldmann: The Parameterized Hardness of the k-Center Problem in Transportation Networks
We study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph $G=(V,E)$ and an integer $k$ are given and a center set $C\subseteq V$ needs to be chosen such that $|C|\leq k$. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers $k$, the highway dimension $h$, and even the treewidth $t$. Moreover, under the Exponential Time Hypothesis there is no $f(k,t,h)\cdot n^{o(t+\sqrt{k+h})}$ time algorithm for any computable function $f$. Thus it is unlikely that the optimum solution to k-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! (Joint work with Dániel Marx)
Pavel Hubáček: On Constant-Round Statistical Zero-Knowledge
I will show how to overcome technical challenges when designing constant-round statistical zero-knowledge proofs. Specifically, I will describe an unconditional transformation from any honest-verifier statistical zero-knowledge protocol to a protocol where the statistical zero-knowledge property holds against arbitrary verifiers.
