Project news


Radio coverage with CoSP researcher

CoSP researchers participated in Prague at 8th Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms, and Applications. It was for Czech and US REU students part of CoSP training.

The conference was organized by Martin Loebl, CoSP lead researcher. It had about 130 participants. „There were speakers from the United States (from Carnegie Mellon University), South Korea, France, Italy, England, Norway…“

Nicolas Trotignon, CoSP led researcher at CNRS, gave an interview for the French version of Radio Prague International here.


Programme of REU 2022 in Prague

MONDAY AUG 1 - STUDENT WORKSHOP


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.



TUESDAY AUGUST 2

Morning: possible visit of MCW or work on problems


14:00 - 16:00 Jiri Fink
Title: Exact and heuristic algorithms for Steiner tree problem
Abstract: We will discuss various approaches to obtain solutions for Steiner tree problem. Exact algorithms based on Integer linear programming provide optimal solutions for small graphs. For larger graph, feasible solutions can be obtain using simple greedy rules which can be improved using various local search methods or evolutionary algorithms.



WEDNESDAY AUGUST 3

Morning: possible visit of MCW or work on problems


14:00 - 16:00 Vahideh Keikha
Title: Polygon Inclusion Problem
Abstract: In this lecture, we discuss the polygon containment problem and the basic geometric properties and data structures for this problem. We study classic algorithms and their failures on general variants besides novel methods to solve this problem in high dimensions.



THURSDAY AUGUST 4

Morning: possible visit of MCW or work on problems


14:00 - 16:00 Martin Loebl
Title: Optimisation by Enumeration
Abstract: We discuss a curiour way how to efficiently solve the Max Cut problem on 2-dimensional surfaces.


1. 8. 2022 will be CoSP student workshop in Prague

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.


CoSP resumes after COVID - REU 2022 at Rutgers in person

We are glad to announce that researchers started again travelling abroad on secondments with CoSP after a pause enforced by COVID-19 pandemic. Michal Koucky visited Rutgers in April 2022.

In the end of May, 10 young talented researchers went from Charles University (CZ) to Rutgers University (US) in order to participate in Research Experience for Undergraduates 2022 (REU 2022). On June 6 2022, students presented the research problems on which they will work on during their secondment.


 Understanding non-monotonicity for 2 independent items - David Sychrovsky, Jachym Mierva

 Designing non-manipulable tournament rules - Jan Soukup, David Miksanik

 Complexity questions derived from Graph Cities – Jan Bronec

 Cycle polytope triangulations and persistent graphs - Gaurav Kucheriya

 Rate 1 Non-malleable codes for polysize tampering - Svetlana Ivanova and Guillermo Gamboa

Fine-grained Space Complexity – Tung Anh Vu

GKR: Journey to NIZK - Ilia Zavidnyi


The training at Rutgers continued with an excellent talk of Misha Khonanov with the title "Regular languages and cobordisms of decorated manifolds".

Abstract: Regular languages constitute a simple class of languages that can be described via finite state automata. We explain a recently found enhancement of regular languages, extending them to an invariant of one-dimensional cobordisms (1-manifolds stretched between two 0-manifolds) with decorations. This approach requires using a circular language as a regularizer and leads to a categorical extension of these familiar concepts. Various necessary concepts, including those of a cobordism, the Boolean semiring and semimodules over it, will be explained in the talk, which is based on a joint recent work with Mee Seong Im. 

The recording of the talk is here.


CoSP REU 2021 final presentations

REU 2021 (Research Experience for Undergraduates) is again due to the corona virus pandemy taking place online. The participation has been really successful, here are the final presentations which involve students from Prague.

David Ryzák and David Sychrovsky have been be working with Ron Holzman (Princeton University) REU_final (1).pdf

Sasha Sami and Vishal Ramesh have been working with Eric Allender (Rutgers University) REU_final (2).pdf


CoSP REU lecture June 29 2021 by Michail Tyomkyn

Title: Weak saturation on graphs and hypergraphs.

Misha Tyomkyn, Charles University Prague

video available here

Suppose a pandemic spreads on the edges of a graph G as follows. Initially a subset of edges are infected. If at any point two out of three edges forming a triangle in G are infected, the third edge becomes infected too.

Continue until no further infections are possible. What we have just described is known as the weak saturation process, and can be defined for any fixed graph H in place of a triangle. It leads to a variety of interesting questions, most importantly, what is the smallest number of initially infected edges that would guarantee every edge of G to become infected? We will survey some classical and present some new results. Joint work with Denys Bulavka and Martin Tancer.


CoSP REU lecture June 22 2021 by Martin Tancer

Title: Necklace splitting on trees

Martin Tancer, Charles University Prague 

video available here

In the classical necklace splitting problem k thieves steal an open-ended necklace with t different types of gems. The number of gems of each type is divisible by k. The target of the thieves is to split the necklace with as few cuts as possible so that they can distribute the pieces so that each thief gets the same number of gems of each type as the other thieves. In this variant, it is well known that (k-1)t cuts are sufficient and for some necklaces also necessary.

During the talk, I will discuss the variant of this problem when the necklace is arranged along the tree. This setting offers several variants of the problem. I will show a combinatorial solution and a geometric solution of some of the variants. The talk is based on joint discussions with Martin Loebl.


REU 2021 (Research Experience for Undergraduates) (remotely)

REU 2021 (Research Experience for Undergraduates) is again due to the corona virus pandemy taking place online. 5 students from Charles University Prague established collaboration with their mentors at Rutgers University (USA) and Princeton University (USA).

David Ryzák and David Sychrovsky will be working with Ron Holzman (Princeton University)

Sasha Sami and Vishal Ramesh will be working with Eric Allender (Rutgers University)


CoSP Midterm Meeting

Date: 10th September 2020 - 11th September 2020

Place: online through ZOOM; zoom details in the beginning of September

Participants: representatives of CUNI, Technion, CNRS, represeantatives of secondees and host institution researchers


REU 2020 final presentations

REU 2020 (Research Experience for Undergraduates at Rutgers University) came into its final phase. Students held their final presentations on 22/07/2020 and 23/07/2020. More information about REU 2020 is available here. The whole event was supported by CoSP project.

We are publishing Charles University's student presentations.


Optimal starting state for a deterministic scan.pdf

High_School_Partitions_final_presentation.pdf

Antipodal Monochromatic Paths in Hypercubes.pdf

Delta coloring in the graph streaming model.pdf