We would like to announce that CoSP 2022 student workshop will take place on 1st August 2022 at Malá strana building of Faculty of Mathematics and Physics.
Date: 1. 8. 2022
Place: MFF UK, Malostranské náměstí 2/25, 118 00 Praha 1, Czechia
10:00-10:50
Henry Fleischmann
Title: Hardness of Approximation or Steiner Trees in Metric Spaces
Abstract: In this talk we discuss new hardness of approximation bounds for the Hamming and $$l_1$ Steiner tree problems based on a reduction from Vertex Cover. We then discuss progress toward showing APX-hardness of the Euclidean Steiner tree problem for n points in n dimensional space.
11:00-11:50
Tung Anh Vu
Title: Generalized k-Center: Distinguishing Doubling and Highway Dimension
Abstract: We consider generalizations of the k-Center problem in graphs of low doubling and highway dimension. For the Capacitated k-Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are k, the number of outliers and the doubling dimension of the supplier set. On the other hand, we show that for the Capacitated k-Center problem, which is a special case of CkSwO, obtaining a parameterized approximation scheme (PAS) is W[1]-hard when the parameters are k, and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.
11:50-13:00
Lunch break
13:00-13:50
Gaurav Kucheriya
Title: Edge-ordered graphs with almost linear extremal functions
Abstract: The central theme of Turán type graph problems is to maximize the number of edges a graph can have, under certain (forbidding) conditions, which is known as its extremal function. Here we consider graphs with edge-order, that is, the edges are linearly ordered. A paper by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos and Vizer started the study of these type of extremal problems for edge-ordered variant.
Since the extremal function for unordered graphs follows a dichotomy: the function is linear if and only if the forbidden graph is forest. So similar dichotomy was conjectured for edge-ordered and vertex-ordered graphs. Here, I present the solution that settles it in the former case, which is joint work with Gabor Tardos.
14:00-15:30
Lawrence Frolov
Title: On the unique existence of Jello
Abstract: The days of spring, will surely bring, the birds and bees cavorting. But since I am a gentleman, I’d much rather be proving the well posedness of differential equations. In this talk we do precisely that, prove the existence of unique solutions for a wide range of differential equations which frequently appear in the study of physics. By the end of the talk, we hope to prove the well-posedness of Jello, which is modeled via an infinite system of point particles which are coupled by springs.
Posted on 2022-07-18