2 citations · 2 across the 3 of their papers we have counts for
6 papers
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…
On Protocols for Monotone Feasible Interpolation
Lukáš Folwarczný
Feasible interpolation is a general technique for proving proof complexity lower bounds. The monotone version of the technique converts, in its basic variant, lower bounds for mono…
Online Algorithms for Multi-Level Aggregation
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka +7
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T t…
IV-matching is strongly NP-hard
Lukáš Folwarczný, Dušan Knop
IV-matching is a generalization of perfect bipartite matching. The complexity of finding IV-matching in a graph was posted as an open problem at the ICALP 2014 conference. In this…
General Caching Is Hard: Even with Small Pages
Lukáš Folwarczný, Jiří Sgall
Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes…