2 citations · 2 across the 2 of their papers we have counts for
4 papers
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…
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…