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: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -

Abstract: -