This has been a busy week for doctoral defenses for me: I attended three, participating in the committees for the last two.

The first, on Monday, was Ryuto Kitagawa, a student of Mike Goodrich. Ryuto came to UCI through a recommendation from Mike’s former student, Nodari Sitchinava at the University of Hawaii. His thesis concerned parallel data structures, based on three of his publications. Two of these concern invertible Bloom filters and invertible Bloom lookup tables, data structures that can handle a streaming sequence of insertions and deletions of keys or key/value pairs (respectively) and allow lookups in the resulting set whenever the number of remaining elements is below the set capacity of the data structure, even if it might have gone far above capacity earlier. Normally these use space linear in the capacity and are decoded sequentially, but “Parallel Peeling of Invertible Bloom Lookup Tables in a Constant Number of Rounds” (SOFSEM 2025) gives a constant-time decoding algorithm at the expense of a logarithmic space penalty. In “Dynamic Accountable Storage: An Efficient Protocol for Real-Time Cloud Storage Auditing”, Ryuto applies these data structures to a problem of verifying that cloud storage providers still have a valid copy of your stored data. Another part of the thesis concerns a parallel B-tree data structure, from Ryuto’s paper “Parallel Joinable B-Trees in the Fork-Join I/O Model” (ISAAC 2025).

Next, on Tuesday, was the turn of Ofek Gila, another student of Mike, whom Mike recruited when Ofek was a UCI undergraduate. I’ve already discussed the work that Ofek included in his thesis in several previous posts here. His paper “Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent” won the best paper award at WADS 2023; it provides a variation of the zip tree data structure of Bob Tarjan, Caleb Levy, and Stephen Timmel that uses fewer random bits per node and that maintains the same depth that one would get from a random binary search tree. Although this depth is larger than a perfectly balanced search tree by a factor of \(\ln 4\approx 1.386\), Ofek conjectures that it is optimal for strongly history-independent binary search trees with logarithmic update costs. “Zip-tries: simple dynamic data structures for strings” (ACDA 2025) extends similar ideas of zipping-based updates and few random bits per node to dynamic string dictionary data structures; I am a coauthor on this one and posted about it here. Finally, his “Highway Preferential Attachment Models for Geographic Routing” won the best paper award at COCOA 2023; it is coauthored with recent doctorate Evrim Ozel. It is related to a model of small-world networking by Jonathan Kleinberg, in which adding random long-range connections to a grid, with probability inverse-square in the connection distance, preserves bounded average degree while allowing greedy routing methods to find short paths. Ofek and Evrim’s work gives more structure to the long-range connections by assigning each node a randomly chosen length range (with diminishing probabilities for longer connections) and only allowing connections between nodes with similar ranges. The result is a family of small-world networks that preserve the general features of Kleinberg’s model but for which greedy routing produces much shorter paths, only slightly above logarithmic in length.

Finally, this morning I participated remotely in the defense of Clément Rambaud, at the Université Côte d’Azur in France. Clément already has many deep publications in graph minor theory. The foundation of this theory is the Robertson–Seymour theorem, that every family of graphs closed under taking minors (subgraphs of edge contractions) can be characterized by finitely many graphs that are forbidden as minors, in the same way that the planar graphs are characterized by the two forbidden minors \(K_5\) and \(K_{3,3}\). Clément’s thesis revolved around a conjecture of Robin Thomas, that in the same way, graph parameters that behave monotonically under taking minors should be characterized by finitely many well-defined families of graphs. Classical examples are that a graph has small treewidth iff it has no large square grid minor, that it has small pathwidth iff it no large complete binary tree minor, and that it has small treedepth iff it has no long path minor. Clément introduced a \(k\)-treedepth parameter, interpolating between treedepth and treewidth, and defined by structural decompositions allowing \((<k)\)-clique-sums and adding an apex at the expense of increased depth. He showed that these are characterized by forbidden rectangular grid minors, where the small dimension of the grid controls the parameter \(k\) (up to a constant factor) and the large dimension controls the \(k\)-treedepth. His thesis went on to explain, to a large extent, the phenomenon that local versions of graph parameters (where one studies the relation of the parameter value to the diameter of a subgraph) are often controlled by forbidden minors that add one apex vertex to the forbidden minors for global properties: local treewidth is controlled by forbidden apex graphs, local pathwidth is controlled by apex-trees, and local treedepth is controlled by fans (apex-paths), etc. A third part of the thesis used the main technical tool for studying these local properties, rooted graph minors, to study centered colorings of graphs; these can be thought of as a way of covering a given graph with a small number of bounded-treedepth subgraphs, allowing fast algorithms for subgraph isomorphism and related problems. For minor-closed graph families one needs a number of colors that is polynomial in the desired treedepth bound, but the exact polynomial is unknown, even for planar graphs. Clément’s thesis strengthened the bounds on how many colors are needed, to within one in the exponent of the polynomial.

Congratulations, Ryuto, Ofek, and Clément!

(Discuss on Mastodon)