Project news

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.

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

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.

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) 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)

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 (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

REU 2020 (Research Experience for Undergraduates) is due to the corona virus pandemy taking place online. 12 students from Charles University Prague established collaboration with their mentors at Rutgers University (USA). Students presented their projects on 2nd June 2020.

antipodal-monochromatic-paths-in-hypercubes.pdf

delta-coloring-in-the-graph-streaming-model.pdf

Updating-colorings.pdf

High-School-Partitions.pdf

Starting summer 2020 Shira Zerbib is coordinating a CoSP Zoom seminar on topological combinatorics, replacing a conference on the same topic that was supposed to take place in Prague this summer and was cancelled due to COVID-19. 

The talks will be given on Tuesdays and Thursdays at 8:00am (CDT), as of June 30, 2020. 

CoSP student workshop 2020 organised by Michael Skotnica will be held remotely on July 29, 2020.