ITU Seminar on Algorithms and Complexity 

Abstract: Data structures are fundamental in the realm of computation theory and have been studied for many decades. Proving lower bounds for query times has been a notoriously difficult task, with many data structure problems still having wide gaps between upper and lower bounds. Similarly, parallel computation has been studied in many forms for almost as long as data structures with the most powerfull models being amazing for proving lower bounds. We explore the natural intersection of these two topics, i.e. can we prove lower bounds for query times in data structures that allow for queries and updates that use parallel computation? This is so far almost completely unexplored, but by combining techniques from both fields we acquire new lower bounds for a range of problems. We also present some data structure constructions as well as discuss the limitations of the methods developed.

Abstract: Joint work in progress with Bianca Oancea and Hoang La. Suppose an unknown graph can only be probed through an oracle that reports, for any small set of vertices, a coarse description of the subgraph they induce rather than the subgraph itself. How coarse can this description be before the graph stops being recoverable? We identify a short list of pairs of small graphs that the description must keep apart, and show that separating them is enough to reconstruct any sufficiently large graph. The proof yields an explicit algorithm.

Abstract: Two graphs G and H are homomorphism indistinguishable over a graph class F if, for every graph F ∈ F , the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs. Subsequently, homomorphism indistinguishability relations of a long list of natural graph classes have been equated with natural graph isomorphism relaxations.

Given the wealth of such results, Atserias, Kolaitis and Wu asked for an axiomatic characterisation of homomorphism indistinguishability relations. By exhibiting topological and geometric structure associated with homomorphism indistinguishability, we derive such an axiomatic characterisation. Here, a central ingredient is a novel characterisation of graph parameters of the form hom(F, -) for some graph F alternative to a previous result of Lovász and Schrijver. Moreover, we investigate the topology of homomorphism indistinguishability and discuss repercussions for Ulam’s reconstruction conjecture.

Joint work with Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson, Gian Luca Spitzer, and Peter Zeman

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -