6th Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)
The meeting takes place on Friday December 1, 2017. All lectures are in the building of MFF UK in Malá Strana, Malostranské nám. 25.Program
| 9:30 (Small Aula, 1st floor) | Andreas Emil Feldmann: Parameterized approximation algorithms for directed Steiner network problems in bidirected graphs |
|---|---|
| 10:00 (Small Aula, 1st floor) | Jiří Fink: Matchings extend to 2-factors in Carthesian graphs |
| 10:30 | coffee break |
| 11:00 (Small Aula, 1st floor) | Tommaso Moraschini (Institute of Computer Science, CAS): A correspondence between logical translations and semantic transformations |
| 11:30 (Small Aula, 1st floor) | Pavel Hrubeš (Institute of Mathematics, CAS): How to generalize Descartes' rule of signs? |
| 12:15 | lunch in the restaurant in the basement of the faculty building |
| 14:00 (Room S5, 2nd floor) | Moni Naor (Weizmann Inst., Israel), 106th Mathematical Colloquium: White-box vs. black-box search problems: A cryptographic perspective |
| 15:00 | coffee break |
| 15:30 (Small Aula, 1st floor) | Jan Ekstein (Univ. of West Bohemia, Plzeň): Bounding the distance among longest paths in a connected graph |
| 16:00 (Small Aula, 1st floor) | Pavel Hubáček ARRIVAL: next stop in CLS |
Andreas Emil Feldmann: Parameterized approximation algorithms for directed Steiner network problems in bidirected graphs
Given an edge-weighted directed graph G=(V,E) and a set of d terminal pairs (s_1,t_1),...,(s_d,t_d), the objective of the Directed Steiner Network (DSN) problem is to compute the cheapest subgraph N of G such that there is an s_i -> t_i path in N for every i. This problem is notoriously hard, even in the realm of parameterized approximation: for the well-studied parameter k=|{s_i,t_i}|, i.e. the number of terminals, it was recently shown by [Dinur & Manurangsi, 2017] that under Gap-ETH no d^{1/4-o(1)}-approximation is possible for DSN in f(k)*poly(n) time, for any function f(k). The main question we explore is: what approximation factors and runtimes are possible for special cases of DSN when parametrizing by the number of terminals k?
For problems related to DSN it has been fruitful before to analyze the structure of the optimum in order to obtain approximation and FPT algorithms. Therefore, we consider the DSN_K problem, where we need to compute the optimum network contained in some class K of graphs. If K for instance is the class of planar graphs, then this generalizes several well-studied special cases, such as DSN on planar input graphs, but also the Directed Steiner Tree problem on general input graphs. Our main result proves that if additionally the input is bidirected, then a parameterized approximation scheme exists if we aim to compute the planar optimum. We also provide several hardness results that show that our obtained runtime is the best possible for this special case, while at the same time no parameterized approximation scheme exists for any generalization of this special case. We also consider the Strongly Connected Steiner Subgraph (SCSS) problem as another special case, which cannot be captured by DSN_K for any non-trivial class K. We prove that a known parameterized 2-approximation is best possible for SCSS, and that on bidirected input graphs the problem is FPT for parameter k.
Jiří Fink: Matchings extend to 2-factors in Carthesian graphs
Let G' be the Cartesian product of a graph G and a 4-cycle. We prove that for every graph G every matching of G' can be extended to a 2-factor in G'. This statement is a generalization of a conjecture by Vandenbussche and West which asserts that every matching of a hypercube can be extended to a 2-factor.
Tommaso Moraschini (Institute of Computer Science, CAS): A logical and algebraic characterization of adjunction between quasi-varieties
As soon as the first non-classical logics were developed, it became clear that the possibility of exploiting this variety of logical systems depends on our capability of drawing translations between them, which allow to study their interplay on common grounds. Motivating cases suggests that translations between logics come in pair with some tranformations between their semantics. The aim of this talk is to show that this is not a coincidence, by describing a general one-to-one correspondence relating translations between logics and adjunctions between their algebraic semantics. The main result takes the form of a combinatorial description of right adjoint functors between quasi-varieties of algebras.
Pavel Hrubeš (Institute of Mathematics, CAS): How to generalize Descartes' rule of signs?
Descartes rule' of signs gives an estimate on the number of real roots of a polynomial in terms of the number of its coefficients. We discuss variants and generalizations of the rule, with some potential applications to arithmetic circuit complexity.
Jan Ekstein: Bounding the distance among longest paths in a connected graph
It is easy to see that in a connected graph any 2 longest paths have a vertex in common. For k>=7, Skupień in 1966 obtained a connected graph in which some k longest paths have no common vertex, but every k-1 longest paths have a common vertex. It is not known whether every 3 longest paths in a connected graph have a common vertex and similarly for 4, 5, and 6 longest paths. Fujita et al. in 2015 gave an upper bound on the distance among 3 longest paths in a connected graph. In this paper we give a similar upper bound on the distance between 4 longest paths and also for k longest paths, in general.
Pavel Hubáček: ARRIVAL: next stop in CLS
We study the computational complexity of ARRIVAL, a zero-player game on switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. It was shown by Dohrau et al. that the problem of deciding termination of this game is contained in the intersection of NP and coNP. Karthik C. S. recently introduced a search variant of ARRIVAL and showed that it is contained in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of ARRIVAL. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of ARRIVAL is contained in the intersection of UP and coUP. Second, we show that the search variant of ARRIVAL is contained in the complexity class CLS. Our main technical contribution is an efficiently verifiable characterization of the unique witness for termination of the ARRIVAL game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete.
Joint work with Karel Král and Veronika Slívová.
