Graph communication protocols are a generalization of classical communication protocols to the case when the underlying graph is a directed acyclic graph. Motivated by potential applications in proof complexity, I study variants of graph communication protocols and relations between them.
So far, my results establish the following hierarchy: Protocols with disjointness are at least as strong as protocols with equality and protocols with equality are at least as strong as protocols with inequality. Furthermore, we establish that protocols with a conjunction of two inequalities have the same strength as protocols with equality. Lower bounds for protocols with inequality are known. Obtaining lower bounds for protocols higher in the hierarchy would direcly lead to applications in proof complexity. In particular, lower bounds for resolution with parities (R(LIN)) and DNF-resolution (DNF-R) would be obtained this way.
The computational hardness of general caching in the offline setting has been shown to be strongly NP-hard only recently, but under the assumption that pages as large as half of the cache size are allowed. In practical applications, it is usually assumed that pages are very small in comparison with the cache size. We prove that the problem is already strongly NP-hard when page sizes are restricted to be one, two or three. This result appeared as the paper General Caching Is Hard: Even with Small Pages in the proceedings of ISAAC 2015.
The thesis also contains an alternative proof for the characterization of work functions by layers in the case of uniform caching (paging) and the proof is further generalized to the case when the cache size varies over time. Two simple algorithms based on these results are developed in the last chapter of the thesis.
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted rooted tree T, and have to be served eventually. A service is defined as a subtree X of the tree T that contains its root. This subtree serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees.
In our paper Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: Online Algorithms for Multi-Level Aggregation, we present the very first algorithm for the online variant of the problem which is competitive for an arbitrary (but fixed) depth of the tree T. A set of related results on MLAP is also given in the paper, but I was not involved in producing these results.
The competitive ratio of the algorithm is exponential in the depth of T and no non-constant lower bound on the competitive ratio is known. Inventing a better algorithm or deriving a super-constant lower bound remains therefore an important challenge.
IV-matching is a specific generalization of perfect bipartite matching to layered graphs and the complexity of finding IV-matching in a graph was posted as an open problem at the conference ICALP 2014. Together with Dušan Knop, we solved the problem during the summer program REU 2014. A simple proof that the problem is strongly NP-hard, already in the simplest case of four layers, is given in our note.