|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
|
|
Graph communication protocols
Folwarczný, Lukáš ; Pudlák, Pavel (advisor) ; Sgall, Jiří (referee)
Graph communication protocols are a generalization of classical communi- cation protocols to the case when the underlying graph is a directed acyclic graph. Motivated by potential applications in proof complexity, we study variants of graph communication protocols and relations between them. The main result is a comparison of the strength of two types of protocols, protocols with equality and protocols with a conjunction of a constant num- ber of inequalities. We prove that protocols of the first type are at least as strong as protocols of the second type in the following sense: For a Boolean function f, if there is a protocol with a conjunction of a constant number of inequalities of polynomial size solving f, then there is a protocol with equality of polynomial size solving f. We also introduce two new types of graph communication protocols, protocols with disjointness and protocols with non-disjointness, and prove that the first type is at least as strong as the previously considered protocols and that the second type is too strong to be useful for applications.
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
guest ::
