10th workshop of the Center of Modern Computer Science
10. seminář Centra moderní informatiky
The tenth workshop of the Center of Modern Computer Science will take place on Monday December 19, 2016 in the Malá Strana building.
Centrum moderní informatiky zve na desátý seminář. Přednášky juniorů centra se konají v průběhu programu v pondělí 19. 12. 2016 v budově MFF UK na Malé Straně.
| 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 |
| 16:30 (room S6, 2nd floor) | Hans Raj Tiwary: Extension complexity of Formal languages |
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.
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.
