Project news

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.

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.

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.

We announce that CoSP workshop on matchings will be organized at Charles University from 24th to 26th October 2022. The workshop brings together students and researchers working in broader aspects of matchings in algorithms and game theory.

Place: Faculty of mathematics and Physics, Charles University, Malostranske namesti 25, Prague, Czech Republic

Program and abstracts

24th October 2022

Room: Malá aula

14:00 Ole Jann (CERGE-EI): An Informational Theory of Privacy

Abstract: Privacy of consumers or citizens is often seen as an inefficient information asymmetry, as exemplified by the saying that "if you have nothing to hide, you have nothing to fear". We challenge this view by showing that privacy can increase welfare in an informational sense. It can also improve information aggregation and prevent inefficient statistical discrimination. We show how and when the different informational effects of privacy line up to make privacy efficient or even Pareto-optimal. Our theory can be applied to decide who should have which information and how privacy and information disclosure should be regulated. We discuss applications to online privacy, credit decisions and transparency in government.

15:00 Katarína Cechlárová (UPJS Kosice): Matchings in theory and practice

Abstract: Matching problems arise in different situations and concern various activities of people: assignment of students to schools, search for donors of kidneys or houses for tenants, or even marriage partners. Obviously, different circumstances lead to different desirable properties of the
matching that is sought.

In this talk we motivate and formally introduce the basic notions of stability and fairness and show how the language of mathematics, in particular graph theory, can help in the description of the desiderata, design and analysis of efficient algorithms. Finally we report on practical problems where we used methods of matching theory and succeeded in improving the procedures implemented in practice.

16:00 Discussion

25^th October 2022

Room: S8

14:00 Jozef Barunik (IES FSV UK): Deep Learning in Economics and Finance

Abstract: While machine learning methods are widely used in many areas of our lives, it is rather scarce in finance where we need to understand the decision making of agents who make decisions based on their preferences and maximize their utility. Growing evidence for irrational decisions of such agents invalidates traditional economic approaches and irrationality in the agent's behavior caused by the various factors described by social sciences, mainly psychology and sociology (emotions, herd behavior, social norms, etc.) changes the way we view the problem. Nowadays, it is still hard to quantify the qualitative and quantitative impacts of such irrationalities directly. However, with the currently available datasets containing lots of information, as well as algorithms used by machine learning and computer power enables us to study these problems in a more complex ways. The working package Finance and Society will focus on the development of such methods of quantitative analysis based on machine learning to help us understand the impact of finance and financial sector on society.

15:00 Martin Loebl (KAM, MFF UK): Critical Goods Distribution System

I will propose a new distribution system for crises supporting autonomous behaviour.

16:00 Discussions

26^th October 2022

Room: Malá aula

14:00 Martin Schmid (KAM, MFF UK and EquiLibre Technologies): New Horisons of Algorithmic Game Theory

Game theory has always been a fundamental theoretical tool in analysing markets and economy (most notably, John F. Nash receiving the Economic Sciences Prize for his work on equilibrium theory). There has been great progress in algorithmic game theory in recent years. Poker, Ches, Go and other games have seen historical milestones thanks to reinforcement learning algorithms and algorithmic game theory. We will talk about the recent breakthroughs and about the possible and interesting future directions

15:00 Goals and Open Problems

Summer training of talented young researchers from Charles University and Rutgers University has started. In 2023, 11 researchers from Charles University and 6 from Rutgers University participate in the Research Experience for Undergraduates (REU 2023). The summer training lasts from June until the beginning of August 2023.

More information is available here at REU 2023 webpage here. Participants presented the research projects, on which they will work during REU, to peers and mentors on 05/06/2023. CUNI's presentations are below.

KT Graph Orientations

Division Game

Hardness of Approximation for Clustering Objectives

Steiner Trees for Regular Simplexes\

REU will continue with the training programme at Rutgers University with work on research projects; technical training (for example lectures, workshops or site visit); and new competences in the area of transferable skills. The second half of REU will take place in Prague in the last weeks of July and beginning of August 2023.

Research Experience for Undergraduates (REU) 2023 will continue in Prague starting from 24.7.2023. The event is supported by CoSP project, which received funding from  the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie action. The programme will take place at the premises of Charles University, Malostranské náměstí 2/25, Prague 1.

24.7.2023 Monday

10:00 Jan Kynčl: On Erdos-Szekeres Theorem

(lecture and presentation of the problems to work on)

Afternoon: Work on the problems followed by solutions and discussion

25.7.2023 Tuesday

10:00 Martin Balko: Annoying (but beautiful) visibility problems

(lecture and presentation of the problems to work on)

Abstract: In this talk, we will survey and explore known problems and conjectures about visibility in point sets in the plane. Here, two points p and q are visible in a planar point set P if there is no point of P lying between p and q on the line segment pq. All these problems have couple of things in common: they are easy to state but, somewhat annoyingly, are also very difficult to solve and most of them remain open. To give an example, we will discuss the Blocking conjecture about placing n points in the plane in general position with the smallest number m of blocking points between them so that no two of the n points are visible in the resulting set of n+m points.

Afternoon: Work on the problems followed by solutions and discussion

26.7.2023 Wednesday

10:00 Jan Volec: Lopsided Lovasz Local Lemma

(lecture and presentation of the problems to work on)

Abstract: In the first part, we are going to recall the so-called first moment method and Markov's inequality, and apply them to a few problems in combinatorics and number theory.

In the second part, we introduce symmetric, general and lopsided variants of Lovasz Local Lemma, and use the lemma to improve some of the results from the first part.

We conclude by presenting the framework of Lu and Szekely on applying the Lopsided Lovasz Local Lemma in the setting of random injections, and use it to prove the following: if the edges of K_n are colored in such a way that every vertex sees every color on its incident edges at most n/100 times, then the coloring contains a properly colored Hamilton cycle.

Afternoon: Work on the problems followed by solutions and discussion

27.7.2023 Thursday - CoSP student workshop

10:00 - 10:45 Guillermo Gamboa: Sparse metric hypergraphs

Abstract: Given a metric space (X,d), we say y is between x and z if d(x,z)=d(x,y)+d(y,z). A metric space gives rise to a 3-uniform hypergraph that has as hyperedges those triples {x,y,z}, where y is between x and z. Such hypergraphs are called metric. In this talk, we will consider the other direction: Is any given a 3-uniform hypergraph metric? We will present some examples of metric and non metric 3-uniform hypergraphs, as well as introduce a notion of sparsity for these. Finally, we will prove that such sparse 3-uniform hypergraphs are metric.

10:45 - 11:30 Caleb Fong:  Compactness in Combinatorics
Abstract: For many combinatorial problems which have been resolved in the finite setting, a natural question is whether similar results hold in the infinite setting. For these questions, the compactness theorem from first-order logic sometimes comes in handy. In this mostly expository talk, we will explain this theorem, talk about its applications and deficiencies, and (if time permits) talk about a research problem which made me care about compactness in the first place.

11:30 - 12:15 Sumi Vora: A Theoretical Survey of Graph Neural Networks (GNNs)
Abstract: Graph Neural Networks (GNNs) are a type of deep learning model that can operate on graph structured data. In this talk we provide a survey of the theoretical foundations for graph neural networks, deriving the necessary formulas for updating node embeddings and minimizing loss. We’ll conclude with a discussion of algorithms for fairness and explainability for GNNs.

12:15 - 14:00 Lunch break

14:00 - 14:45 Jakub Petr:  Automorphisms of the Symmetric Groups
Abstract: We will go over the basics of Group Theory and get to know the notion of automorphisms. At last, we will show why S_6 is the only symmetric group that can have an outer automorphism.

14:45 - 15:30 Gaurav Kucheriya: Turán-type problems in edge-ordered graphs
Abstract: The main objective of Turán-type graph problems is to maximize the number of edges a graph can have under certain (forbidding) conditions. This talk will give an overview of some popular results in this field. In particular, we will also see the extension of this problem to edge-ordered graphs. Joint work with Gabor Tardos.

28.7.2023 Friday

10:00  David Sychrovský: Algorithmic Game Theory

(lecture and presentation of the problems to work on)

In many real world situations, like minor traffic offenses in big cities, a central authority is tasked with periodic administering punishments to a large number of individuals. Common practice is to give each individual a chance to suffer a smaller fine and be guaranteed to avoid the legal process with probable considerably larger punishment. However, thanks to the large number of offenders and a limited capacity of the central authority, the individual risk is typically small and a rational individual will not choose to pay the fine. We will show that if the central authority processes the offenders in a publicly known order, it properly incentives the offenders to pay the fine. Moreover, the same holds for an arbitrary coalition. 

Afternoon: Work on the problems followed by solutions and discussion

31.7.2023 Monday - 4.8.2023 Friday

Midsummer Combinatorial Workshop

MCW website: https://www.mff.cuni.cz/en/kam/events/mcw/mcw-2023

Students participating in CoSP training organize a yearly CoSP student workshop. This year, it will take place at CUNI 27.7.2023. The student workshop will take place at Malostranské náměstí 2/25, Prague 1, 2nd floor, room S6. The agenda is:

10:00 - 10:45 Guillermo Gamboa: Sparse metric hypergraphs

Abstract: Given a metric space (X,d), we say y is between x and z if d(x,z)=d(x,y)+d(y,z). A metric space gives rise to a 3-uniform hypergraph that has as hyperedges those triples {x,y,z}, where y is between x and z. Such hypergraphs are called metric. In this talk, we will consider the other direction: Is any given a 3-uniform hypergraph metric? We will present some examples of metric and non metric 3-uniform hypergraphs, as well as introduce a notion of sparsity for these. Finally, we will prove that such sparse 3-uniform hypergraphs are metric.

10:45 - 11:30 Caleb Fong:  Compactness in Combinatorics
Abstract: For many combinatorial problems which have been resolved in the finite setting, a natural question is whether similar results hold in the infinite setting. For these questions, the compactness theorem from first-order logic sometimes comes in handy. In this mostly expository talk, we will explain this theorem, talk about its applications and deficiencies, and (if time permits) talk about a research problem which made me care about compactness in the first place.

11:30 - 12:15 Sumi Vora: A Theoretical Survey of Graph Neural Networks (GNNs)
Abstract: Graph Neural Networks (GNNs) are a type of deep learning model that can operate on graph structured data. In this talk we provide a survey of the theoretical foundations for graph neural networks, deriving the necessary formulas for updating node embeddings and minimizing loss. We’ll conclude with a discussion of algorithms for fairness and explainability for GNNs.

12:15 - 14:00 Lunch break

14:00 - 14:45 Jakub Petr:  Automorphisms of the Symmetric Groups
Abstract: We will go over the basics of Group Theory and get to know the notion of automorphisms. At last, we will show why S_6 is the only symmetric group that can have an outer automorphism.

14:45 - 15:30 Gaurav Kucheriya: Turán-type problems in edge-ordered graphs
Abstract: The main objective of Turán-type graph problems is to maximize the number of edges a graph can have under certain (forbidding) conditions. This talk will give an overview of some popular results in this field. In particular, we will also see the extension of this problem to edge-ordered graphs. Joint work with Gabor Tardos.

CoSP Annual Workshop with the title UNFINISHED will take place November 6-8 2023 in Prague. This workshop aims at highlighting extensively studied but still open conjectures falling into the project's domain.

Here is the poster CoSP workshop 2023 final.pdf

Place: MFF UK Malostranské nám 25, Prague 1, Czechia
Programme: each day 4PM- 6PM, mornings devoted to discussions with the invited speakers

Monday Nov 6, 4th floor, room S1 (discrete mathematics): Sophie Spirkl (zoom talk) and Nicolas Trotignon
Tuesday Nov 7, 4th floor, room S1 (physics and geometry): Marta Pavelka (zoom talk) and Bergfinnur Durhuus
Wednesday Nov 8, 2nd floor, room S7 (theoretical computer science): Michal Koucky (zoom talk) and Ron Holzman

Abstracts:
1. Sophie Spirkl, U. Waterloo, Canada: 2-colouring tournaments
Colouring a tournament means partitioning its vertex set into transitive subsets. Unlike for graphs, even 2-colouring is NP-complete for tournaments. In the graph setting, much progress has been made on determining the complexity of 3-colouring graphs with a forbidden induced subgraph. In the tournament setting, we don't even have a sensible conjecture for which tournaments make 2-colouring easy when excluded.
Jointly left unfinished with Alvaro Carbonero, Sepehr Hajebi and Yanjia Li.

2. Nicolas Trotignon, CNRS, LIP, ENS de Lyon, France: Is there a minimal non-chi-bounded hereditary class?
The "unfinished question" proposed for the workshop is all in the title, except maybe for some needed definitions that are given now, followed by some motivation.
A class of graphs is hereditary if it's closed under taking induced subgraphs. A hereditary class of graph is chi-bounded if there exists a function f such that all graphs in the class satisfy chi(G) <= f(omega(G)). Therefore, a hereditary class C is non-chi-bounded if there exists an integer k such that for all integer l, there exists a graph G in C satisfying omega(G) = k and chi(G) >= l. A non-chi-bounded hereditary class C is minimal if all its proper hereditary subclasses are chi-bounded. Equivalently, C is minimal if for all H in C, the class of H-free graphs from C is chi-bounded (a graph is H-free if it does not contain H as an induced subgraph).
Seemingly, no minimal hereditary non-chi-bounded class is known. It might be that none exists, and proving this would yield a beautiful and general theorem. While it would be interesting for some that some minimal non-chi-bounded class exists, because each such class would be a kind of best-possible source of counter-examples to conjectures stating that a class is chi-bounded.
The talk will present a recent work by Édouard Bonnet, Romain Bourneuf, Julien Duron, Stéphan Thomassé and the speaker, showing that the classical Zykov's construction of triangle-free graphs of high chromatic number is far from being minimal. It contains graphs of high chromatic number with several structural restrictions: low connectivity or presence of twins, and high odd girth.

3. Marta Pavelka, Cornegie Mellon University U.S.A.: On triangulations of 3-spheres

The question ``How many triangulations of the 3-sphere with a given number of tetrahedra are there?'' has been around for a while. It was proposed by Bergfinnur Durhuus and Thordur Jonsson in 1995 in the context of the quantum gravity model and its convergence. Five years later, Mikhael Gromov listed it as one of the fundamental questions of topology. More specifically, it remains an open problem whether there are exponentially many of these triangulations in terms of the number of facets or if there are more. In this talk, we will see the current progress and directions researchers are taking to tackle this question. Moreover, we will look at classes of 3-spheres (or even d-spheres) that are proven to have an exponential size, including the 2-locally constructible spheres.

4. Bergfinnur Durhuus, Copenhagen University, Danemark: Combinatorial Questions in Quantum Gravity

In attempts to formulate a regularized model of quantum gravity one encounters interesting combinatorial problems related to counting certain geometric objects, like combinatorial manifolds, subject to certain (topological) constraints. This lecture will serve to formulate some such questions and to present a few details on their background as well as to discuss some partial results.

5. Michal Koucky, IUUK MFF UK Prague Czech Republic: Locally consistent decomposition of strings with applications to edit distance sketching
In this talk I will present a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness and ignoring poly-log factors). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ.
This decomposition has applications to edit distance sketching and streaming approximate pattern matching algorithms.
Joint work with Sudatta Bhattacharya.

6. Ron Holzman, Technion Israel: Fair Division via Quantile Shares
We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with valuations over bundles of goods. To capture fairness, we adopt the notion of shares, by which every agent has a fair share, according to some definition, and an allocation is considered fair if the value of every agent for her bundle (weakly) exceeds her fair share. We introduce a new notion of shares in which an agent deems a bundle fair or unfair based on how it compares to her value in a uniform allocation of the goods. Specifically, for every q in [0,1], a bundle is q-quantile fair if the probability of getting a (weakly) worse bundle in a uniform allocation is at least q. The question that drives us in this work is the feasibility of q-quantile shares. Namely, for what values of q, every profile of (monotone) valuations admits a q-quantile fair allocation.
Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdos Matching Conjecture.
This is joint work with Yakov Babichenko, Michal Feldman and Vishnu V. Narayan.

Rutgers University organizes a workshop called "DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools" in collaboration with CoSP. The event will take place from 6th May 2024 until 9th May 2024. One of the co-organizers is prof. Michal Koucký from Charles University.

More details are available here: http://dimacs.rutgers.edu/events/details?eID=2733

The event will take place at DIMACS Center of the Rutgers University. Researchers from Europe involved in the CoSP project will participate in the workshop.