5th Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)
The meeting takes place on Monday December 19, 2016. All lectures are in the building of MFF UK in Malá Strana, Malostranské nám. 25.Program
| 9:15 (Small Aula, 1st floor) | Tereza Klimošová: Edge-partitioning graphs into paths and trees |
|---|---|
| 9:45 (Small Aula, 1st floor) | Martin Tancer: NP hardness and distiction of topological paramaters, on a discussion with Arkadiy Skopenkov |
| 10:15 | coffee break |
| 10:40 (room S6, 2nd floor) | Rob Morris (IMPA, Rio de Janeiro): The method of hypergraph containers 1 (part of Ramsey DocCourse Prague 2016) |
| 12:30 | lunch |
| 14:30 (Small Aula, 1st floor) | Petr Hliněný (Masaryk Univ., Brno): A short proof of Euler-Poincaré formula |
| 15:00 (Small Aula, 1st floor) | Rostislav Horčík (Institute of Computer Science, CAS): Algebraic approach to valued CSP via non-classical logics |
| 15:30 (Small Aula, 1st floor) | Dmitry Gavinsky (Institute of Mathematics, CAS): On quantum vs. classical communication complexity |
| 16:00 | coffee break |
| 16:30 (room S6, 2nd floor) | Hans Raj Tiwary: Extension complexity of formal languages |
| 17:00 (room S6, 2nd floor) | Antonín Kučera (Masaryk Univ., Brno): Stability in graphs and games |
Abstracts
Tereza Klimošová: Edge-partitioning graphs into paths and trees
In 2006, Barat and Thomassen conjectured that for a fixed tree T, every sufficiently edge-connected graph with the number of edges divisible by |E(T)| has a T-decomposition. That is, the edge set of the graph can be partitioned into isomorphic copies of T. The conjecture was recently proven by Bensmail, Harutyunyan, Le, Merker and Thomasse. Bensmail, Harutyunyan, Le, and Thomasse posed a strengthened version of the conjecture of Barat and Thomassen, that for a fixed tree T, every graph with sufficiently high degree and with the number of edges divisible by |E(T)| has a T-decomposition if it is sufficiently highly edge-connected in terms of maximal degree of T. They proved the strengthened conjecture for T being a path. The talk will contain several extensions of the results above. We give the optimum edge-connectivity bound of the strengthened version of Barat-Thomassen conjecture for paths and we disprove the conjecture for trees of maximal degree at least three. We also prove a relaxed version of the conjecture, showing that for two fixed trees T and T' with coprime numbers of edges, every connected graph with sufficiently high degree has a T,T'-decomposition. Joint work with Stephan Thomasse.
Martin Tancer: NP hardness and distiction of topological paramaters, on a discussion with Arkadiy Skopenkov
In this talk, my aim is to present a result how to distinguish two topological parameters modulo P \neq NP. The result should be (mainly) contributed to Arkadiy Skopenkov; my contribution is limited. However, I want present this result because I believe that it could be of interest of the audience. I will mainly focus on explanation of the computational complexity part of the problem, using the topological part just as a black box; no prior knowledge of topology is expected.
Petr Hliněný: A short proof of Euler-Poincaré formula
We provide a short self-contained inductive proof of famous Euler-Poincar\'e Formula for the numbers of faces of a convex polytope in every dimension. Our proof is elementary and it does not use shellability of polytopes.
Rostislav Horčík: Algebraic approach to valued CSP via non-classical logics
CSP provides a uniform framework to analyze and solve many combinatorial problems. Similarly valued CSP might be seen as a uniform framework to study a wide class of problems coming from combinatorial optimization such as Maximum Independent Set. A major research line in CSP tries to find a boundary between tractable and intractable problems. One of the most successful approaches to classify tractable problems is the algebraic one based on Geiger's result characterizing pp-definability via polymorphisms. A similar approach was investigated also in valued CSP but only for problems using as a valuation structure the set of positive rational numbers extended with infinity endowed with the usual addition. We show that this approach can be taken to a wider setting by generalizing Geiger's result. It turns out that valued CSP can be viewed as CSP over a non-classical logic. Consequently we obtain the generalization of Geiger's result by characterizing pp-definability in relational structures over this logic.
Hans Raj Tiwary: Extension complexity of formal languages
In this talk I will discuss extension complexity as a measure of complexity of formal languages. I will consider compact languages that admit small extended formulations and describe various closure properties. I will also present a sufficient machine characterization for a language to admit small extended formulation. Finally, I will present a few applications of these results in terms of space lower bounds in the streaming model and upper bounds on extension complexity of a few polytopes.
Dmitry Gavinsky: On quantum vs. classical communication complexity
The setting of communication complexity is one of the strongest computational models, as of today, where people have tools to prove "hardness" – that is, where problems are known that don't have efficient solutions. This allows, in particular, to compare the computational power of two communication regimes via demonstrating that certain problem has an efficient solution in one regime, but not in the other. Many researchers have applied this methodology to argue qualitative advantage of quantum over classical communication models; this talk aims to survey some old and new results.
Antonín Kučera (MU Brno): Stability in graphs and games
We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.
