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

10. workshop Centra základů moderní informatiky

The tenth workshop of the Center for Foundations of Modern Computer Science took place on Thursday September 22, 2022, in Kutná Hora as a part of a joint meeting of IUUK and KAM.

Abstracts

Martin Koutecký: Near-optimal, simpler, and augmentation-free algorithms for integer programming

In a breakthrough result, Koutecký, Levin, and Onn [ICALP 2018] have shown integer programming to be fixed-parameter tractable when the constraint matrix has small treedepth and small coefficients. Another milestone were near-linear strongly-FPT algorithms [SODA 2021, ESA 2022] which hinted at a potential paradigm shift: while all previous work in the area worked by iteratively augmenting an initial solution to optimality, their algorithm was based on solving a certain continuous relaxation, showing its solution is close to the integer optimum, and then solving the residual problem.
The aforementioned approach can, however, only work for linear objectives. We show a new approach based on scaling and sensitivity, which handles separable convex objectives, is simpler than previous iterative augmentation methods, and is in a certain sense (almost) optimal.

Pavel Hubáček, On the Complexity of Inefficient Proofs of Existence in Combinatorics

Many famous existential theorems lacking efficient constructive proofs give rise to important computational problems without an obvious efficient algorithm. In my talk, I will introduce computational problems motivated by classical combinatorial theorems such as, for example, the Erdős-Ko-Rado theorem and show that they characterize the complexity classes PPP (Papadimitriou, J. Comput. Syst. Sci. 1994) and PWPP (Jeřábek, J. Comput. Syst. Sci. 2016).

Based on joint work with Romain Bourneuf, Lukáš Folwarczný, Alon Rosen, and Nikolaj I. Schwartzbach