Project news
CoSP resumes after COVID - REU 2022 at Rutgers in person
2022-06-13
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
2021-08-23
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
2021-06-20
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
2021-06-20
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)
2021-05-11
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
2020-08-22
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
2020-07-27
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
Online REU 2020 starts
2020-07-09
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
CoSP ZOOM Seminar on topological combinatorics
2020-06-29
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
2020-06-29
CoSP student workshop 2020 organised by Michael Skotnica will be held remotely on July 29, 2020.