We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic. In contrast with the conjectured simplicity of the transduction quasi-order for monadic second-order logic, the FO-transduction quasi-order is very complex, and many standard properties from structural graph theory and model theory naturally appear in it. We prove a local normal form for transductions among other general results and constructions, which we illustrate via several examples and via the characterizations of the transductions of some simple classes. We then turn to various aspects of the quasi-order, including the (non-)existence of minimum and maximum classes for certain properties, the strictness of the pathwidth hierarchy, the fact that the quasi-order is not a lattice, and the role of weakly sparse classes in the quasi-order.

We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking of any graph class which is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.

Abstract We show that if a countable structure M in a finite relational language is not cellular, then there is an age-preserving $N \supseteq M$ such that $2^{\aleph _0}$ many structures are bi-embeddable with N. The proof proceeds by a case division based on mutual algebraicity.

With increasing popularity of cloud storage, efficiently proving the integrity of data stored on an untrusted server has become significant. Authenticated skip lists and rank-based authenticated skip lists (RBASL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, an RBASL based on block indices falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O ( n ) updates on the data structure for a file with n blocks. To overcome this problem, we introduce FlexList, a flexible length-based authenticated skip list. FlexList translates variable-size updates to O (⌈ u/B ⌉) insertions, removals, or modifications, where u is the size of the update and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, authenticated, rank-based authenticated, and FlexList). We build such a structure in O ( n ) time and parallelize this operation for the first time. We compute one single proof to answer multiple (non)membership queries and obtain efficiency gains of 35%, 35%, and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (dynamic provable data possession (DPDP) with FlexList instead of RBASL) on PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (provable data possession (PDP)) while providing dynamic data support.