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

7. workshop Centra základů moderní informatiky

The seventh workshop of the Center for Foundations of Modern Computer Science took place on Tuesday July 27, 2021, in Prague as a part of MCW XXVI.

Abstracts

Martin Balko: On the expected number of holes in random point sets

For a positive integer d, let S be a finite set of points in R^d with no d+1 points on a common hyperplane. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. 

We study the expected number of holes in sets of n points drawn uniformly and independently at random from a convex body of unit volume. We provide several new bounds and show that they are tight. In many cases, we are even able to determine the leading constants precisely, improving several previous results.

This is based on two joint works with Pavel Valtr and Manfred Schecher.

Hossein Moosaei: Absolute value equation and its challenges

Absolute value equation ( AVE) is a non-differentiable NP-hard problem that has gained more attention from researchers in recent decades.  In this talk, I would like to introduce the AVE in theory and applications and discuss some of its challenges.

Jakub Bulín: Studying CSP algorithms using pp-interpretability

Given a finite relational structure A, the fixed-template Constraint Satisfaction Problem asks if an input structure X admits a relational homomorphism to A. The CSP dichotomy theorem states that CSP(A) is always either in P or NP-complete. The long road towards the proof has led through improved understanding and considerable generalization of various algorithmic approaches but currently culminates in two complex, superficially similar, yet substantially different algorithms. We will discuss how some of the algorithmic approaches can be studied, compared, classified, and decomposed through the lenses of primitive positive interpretability.

Martin Koutecký: Parameterized Complexity of Mixed Integer (Linear) Programming

The state-of-the-art of the parameterized complexity of variable dimension integer programs is that the most important tractable class of IPs are those with small coefficients and small treedepth of the constraint matrix. It is natural to ask whether these algorithms for "pure" IPs can be extended to mixed IPs, i.e., allowing both continuous and integer variables.

We show that the results extend completely in the case of linear optimization, but, quite surprisingly, separable quadratic convex minimization over a mixed set becomes NP-hard quite soon. The positive result about linear minimization relies on the following structural result: there is an MILP optimum with small fractionality, i.e., with all denominators bounded by a function of the parameters. As a consequence, we show that if we change the set of fractional variables only by switching k variables to be integer/fractional, there are always optima of the corresponding instances which are roughly k-away from each other.