Seminar on Foundations of Computing

This research seminar provides a venue for presenting research results concerning algorithm design, discrete mathematics, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA, FORMELA, and LIVE. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

Time and place

The seminar takes place on Monday at 2PM term time in Room C417 in the building of the Faculty of Informatics on a (roughly) weekly schedule.

Spring 2024 – schedule overview

Upcoming speakers

Liana Khazaliya (TU Vienna): Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth

Monday, February 19, 14:00, room C417

Upward Planarity Testing and Orthogonal Planarity Testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth [Orthogonal: GD'19; Upward: SoCG'22]. In this talk, I will show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known n^{O(tw)}-time algorithms cannot be improved to run in time n^{o(tw)} unless the Exponential Time Hypothesis fails.

Joint work with Bart M. P. Jansen, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov

Martin Dzúrik (Masaryk University): Combinatorial Spectra of Graphs

Monday, March 4, 14:00, room C417

Combinatorial spectra of graphs is a generalization of H-Hamiltonian spectra. The main motivation was to made from H-Hamiltonian spectra an operation and develop some algebra in this field. An improved version of this operation form a commutative monoid. The most important thing is that most of the basic concepts of graph theory, such as maximum pairing, vertex and edge connectivity and coloring, Ramsey numbers, isomorphisms and regularity, can be expressed in the language of this operation.

Arxiv preprint avalilable here

Marek Filakovský (Masaryk University): Topological methods for promised homomorphisms - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs

Monday, April 8, 14:00, room C417

A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours [1,...,k] such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).

joint work with Nakajima, Opršal, Tasinato and Wagner

Samuel Braunfeld (Charles University): Some interactions between model theory and structural graph theory

Monday, April 15, 14:00, room C417

We will discuss how model-theoretic concepts concerned with separating tame from wild behavior in classes of infinite structures and with developing a structure theory for the tame classes can be applied to classes of finite structures, interacting with programs in structural graph theory. In particular, these concepts have been behind significant recent progress in determining when the general algorithmic problem of first-order model checking is (fixed-parameter) tractable.

Igor Balla (Masaryk University): Small codes and set-coloring Ramsey numbers

Monday, April 22, 14:00, room C417

Determining the maximum number of unit vectors in R^r with no pairwise inner product exceeding alpha is a fundamental problem in geometry and coding theory. In 1955, Rankin resolved this problem for all alpha ≤ 0 and in this talk, we will show that the maximum is (2 + o(1))r for all 0 ≤ alpha ≪ r^(-2/3), answering a question of Bukh and Cox. Moreover, the exponent -2/3 is best possible. As a consequence, we obtain an upper bound on the size of a q-ary code with block length r and distance (1 - 1/q)r - o(r^(1/3)), which is tight up to the multiplicative factor 2(1 - 1/q) + o(1) for any prime power q and infinitely many r. When q = 2, this resolves a conjecture of Tietäväinen from 1980 in a strong form and the exponent 1/3 is best possible. Finally, using a recently discovered connection to q-ary codes, we obtain an analogous result for set-coloring Ramsey numbers.

Kaushik Mallik (ISTA): Auction-Based Scheduling: A Modular Framework for Multi-Objective Decision-Making

Monday, May 6, 14:00, room C417

Sequential decision-making tasks often require satisfaction of multiple, partially-contradictory objectives. Existing approaches are monolithic, where a single policy fulfills all objectives. I will present auction-based scheduling, a new modular framework for multi-objective sequential decision-making. In this framework, each objective is fulfilled using a separate and independent policy. The policies are then composed through a novel run-time composition mechanism, where at each step, they need to bid from pre-allocated budgets for the privilege of choosing the next action. The bidding encourages the policies to adjust their bids according to their urgencies to act, and whoever bids the highest gets scheduled first. We study the following decentralized synthesis problem: How to compute bidding-equipped policies whose composition will simultaneously fulfill all objectives? I will present solutions of the decentralized synthesis problem for path planning on finite graphs with two temporal objectives.

Jan Böker (Aachen): The Complexity of Homomorphism Reconstructibility

Monday, May 27, 14:00, room C417

Representing graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising applications in database theory and machine learning, where one would like to answer queries or classify graphs solely based on the representation of a graph G as a finite vector of homomorphism counts from some fixed finite set of graphs to G. We study the computational complexity of the arguably most fundamental computational problem associated to these representations, the homomorphism reconstructibility problem: given a finite sequence of graphs and a corresponding vector of natural numbers, decide whether there exists a graph G that realises the given vector as the homomorphism counts from the given graphs.

We show that this problem yields a natural example of an NP^{#P}-hard problem, which still can be NP-hard when restricted to a fixed number of input graphs of bounded treewidth and a fixed input vector of natural numbers, or alternatively, when restricted to a finite input set of graphs. We further show that, when restricted to a finite input set of graphs and given an upper bound on the order of the graph G as additional input, the problem cannot be NP-hard unless P = NP. For this regime, we obtain partial positive results. We also investigate the problem's parameterised complexity and provide fpt-algorithms for the case that a single graph is given and that multiple graphs of the same order with subgraph instead of homomorphism counts are given.

This is joint work with Louis Härtel, Nina Runde, Tim Seppelt, and Christoph Standke.

Alexandru Malekshahian (London): On the typical structure of antichains in the Boolean lattice

Monday, June 3, 14:00, room C417

An old question of Dedekind asks for the number of antichains (monotone Boolean functions) in the Boolean lattice on $n$ elements. After a long series of increasingly precise results, Korshunov determined this number up to a multiplicative factor of (1+o(1)). We revisit Dedekind’s problem and study the typical structure of antichains using tools from probability and statistical physics. This yields a number of results which include refinements of Korshunov’s asymptotics, asymptotics for the number of antichains of a fixed size, and a 'sparse' version of Sperner’s Theorem.

Joint work with Matthew Jenssen and Jinyoung Park.

Felix Schröder (Charles University): The Density Formula for Beyond-Planar Graphs

Monday, June 10, 14:00, room C417

We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in the drawing. We demonstrate its capability by providing several applications: we prove tight upper bounds on the edge density of various beyond-planar graph classes, including so-called $k$-planar graphs with $k=1,2$, fan-crossing / fan-planar graphs, $k$-bend RAC-graphs with $k=0,1,2$, and quasiplanar graphs. In some cases ($1$-bend and $2$-bend RAC-graphs and fan-crossing / fan-planar graphs), we thereby obtain the first tight upper bounds on the edge density of the respective graph classes. In other cases, we give new streamlined and significantly shorter proofs for bounds that were already known in the literature. Thanks to the Density Formula, all of our proofs are mostly elementary counting and mostly circumvent the typical intricate case analysis found in earlier proofs. Further, in some cases (simple and non-homotopic quasiplanar graphs), our alternative proofs using the Density Formula lead to the first tight lower bound examples.

Joint work with Matthew Jenssen and Jinyoung Park.

Teodor Knapik (Université de la Nouvelle Calédonie): Lindenmayer graph languages, first-order theories and expanders

Monday, June 24, 14:00, room C417

Imagined by Kolmogorov in the middle of past century, expanders form remarkable graph families with applications in areas as diverse as robust communication networks and probabilistically checkable proofs, to name just two. Since the proof of the existence of expanders, it took several years to come up with an explicit algebraic construction [Margulis 1973] of some expander families. Their first elementary (combinatorial) construction has been published in 2002 and awarded Gödel Prize in 2009.

In this talk we introduce a framework that captures most of known combinatorial constructions of expanders. It is based on a generalisation of Lindenmayer systems to the domain of graphs. We call this formalism Lindenmayer graph grammars. We indentify a few essential properties which make decidable the language checking problem with respect to first-order sentences. This result is obtained by encompassing a graph language into an automatic structure. By language checking in this specific context we mean the following problem.

Instance: a Lindenmayer graph grammar and a first-order sentence Question: Do there exists a graph in the language for which the sentence holds?

Shibashis Guha (TIFR, India): Strategy synthesis for global window PCTL

Monday, July 15, 14:00, room C417

Given a Markov decision process (MDP) M and a formula Phi, the strategy synthesis problem asks if there exists a strategy sigma such that the resulting Markov chain M[sigma] satisfies Phi. This problem is known to be undecidable for the probabilistic temporal logic PCTL. We study a class of formulae that can be seen as a fragment of PCTL where a local, bounded horizon property is enforced all along an execution. Moreover, we allow for linear expressions in the probabilistic inequalities. This logic is at the frontier of decidability, depending on the type of strategies considered. In particular, strategy synthesis is shown to be decidable when strategies are deterministic while the problem is undecidable for arbitrary strategies.

Joint work with Benjamin Bordais, Damien Busatto-Gaston, and Jean-François Raskin

Gaston Burrull (BiCMR, Beijing, China): On the combinatorial invariance conjecture

Wednesday, July 17, 14:00, room C417

The conjecture posed by G. Lusztig (unpublished in the early 1980s) and independently by M. Dyer (1987) predicts that if the two Bruhat intervals [x, y] and [x', y'] (of possibly different Coxeter systems) are isomorphic as partially ordered sets, then the corresponding Kazhdan–Lusztig polynomials are equal, that is, Px,y(q) = Px',y'(q). This is a fascinating conjecture studied by dozens of mathematicians during the last few decades. In this talk, I will explain some history, partial results, and my little understanding of this topic.