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.