12th workshop of the Center for Foundations of Modern Computer Science

12. workshop Centra základů moderní informatiky

The twelfth workshop of the Center for Foundations of Modern Computer Science took place on Tuesday August 1, 2023, in Prague as a part of MCW XXVIII.

Abstracts

Ida Kantor: Metric spaces with many degenerate triangles

Let (X,d) be a metric space. A triple {a,b,c} of points of X is called a degenerate triangle if d(a,c)=d(a,b)+d(b,c).

Richmond and Richmond (American Mathematical Monthly 104 (1997), 713–719) proved the following theorem: If, in a metric space with at least five points, all triples of points are degenerate triangles, then the space is isometric to a subset of the real line.

We prove that the hypothesis is unnecessarily strong: In a metric space on n points, $\binom{n}{3}-n+5$ arbitrarily placed or $3\binom{n-2}{3}+1$ suitably placed degenerate triangles suffice to guarantee the conclusion. The concept of (weak) hypergraph saturation, well known in extremal graph theory, arises naturally in this context, and our result is slightly reminiscent of Kalai's theorem about rigidity (in the geometric sense, pertaining embedding the graphs into R^d of weakly saturated graphs.

Joint work with Vašek Chvátal.

Jakub Bulín: Short definitions in constraint languages

A first-order formula is called "primitive positive" (pp) if it only uses existential quantifiers and conjunction. Pp-formulas are central in constraint satisfaction since CSP(Γ) can be viewed as deciding the primitive positive theory of Γ, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages Γ is characterized by having "few subpowers", that is, the number of n-ary relations pp-definable from Γ is bounded by 2^p(n) for some polynomial p(n). We will discuss a restriction of this property, stating that every pp-definable relation is definable by a pp-formula of polynomial length; examples include 2-SAT, graph 2-coloring, and solving linear systems over finite fields. We will discuss our conjecture that "short definitions" are actually equivalent to few subpowers, and give main ideas of a proof for a large subclass that, in particular, includes all constraint languages on 3-element domains.

Joint work with M. Kompatscher.