"AlgoComp" is a weekly seminar series hosted by the Theoretical Computer Science Section at the IT University of Copenhagen. The seminars take place every Monday and feature presentations by PhD students, postdoctoral researchers, faculty members, and visiting scholars. The scope of the talks covers all topics of algorithms and complexity, and can range from presenting recently published cutting-edge research to informal and open-ended problem sessions. Attendance is open to everyone, including interested bachelor’s and master’s students.
The seminar is currently maintained by Sarita de Berg and Ivor van der Hoog. If you are interested in giving a talk, don't hesitate to contact debe@itu.dk.
07.09. Magnus Merrild Aarhus University
Title: Cell-Probe Lower Bounds for Data Structures in CRCW PRAM
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.
14.09. Johanne Cohen National Centre for Scientific Research, France
Title: Discovering a graph through a partition oracle
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.
21.09. Tim Seppelt IT University of Copenhagen
Title: Topological and Geometric Perspectives on Homomorphism Indistinguishability
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
05.10. Maximo Perez Lopez Technical University of Denmark
Title: Tighter Bounds for Wheeler Determinization
Abstract: Wheeler automata are a class of finite automata defined by Gagie, Manzini and Sirén [TCS 2017], designed to be compressible and support fast pattern matching of a pattern P in O(|P|log s) time, for an alphabet of size s. Given a Wheeler NFA A, the Wheeler determinization problem is to construct a Wheeler DFA D that accepts the same language as A. We use the notation n_A, m_A for the number of vertices and edges of A, and equivalently n_D, m_D for D. Alanko et al. [SODA 2020] show that D can always be constructed such that n_D<2n_A, and showed an O(n_A^3) algorithm to build it. In this paper, we show how to improve the running time to O(n_A + m_Alog n_A + n_D + m_D) time, almost output-sensitive, using a combination of new techniques and a sorting algorithm of Becker et al [ESA 2023].
Joint work with Philip Bille, Inge Li Gørtz and Simon R. Tarnow.
12.10. Autumn break
Title: -
Abstract: -
19.10. Holger Dell IT University of Copenhagen
Title: Temporal conductance: Consensus and random walks on changing networks
Abstract: How quickly do random walks mix and opinions reach consensus when the underlying graph changes over time? We introduce temporal conductance, which measures whether every cut expands at some point in each time interval, even when individual snapshots are disconnected. If every interval of length Δ has temporal conductance at least ϕ, we prove tight bounds of O((Δ/ϕ)²log n) for the expected mixing time of the lazy random walk and O((Δ/ϕ)n) for the expected consensus time of the lazy synchronous voter model. Joint work with Tatiana Rocha Avila, Jess Enright, John Lapinskas, Laura Larios-Jones, and Kitty Meeks.
26.10. Speaker Affiliation
Title: -
Abstract: -
02.11. Speaker Affiliation
Title: -
Abstract: -
09.11. Sarita de Berg IT University of Copenhagen
Title: -
Abstract: -
16.11. Speaker Affiliation
Title: -
Abstract: -
23.11. Speaker Affiliation
Title: -
Abstract: -
30.11. Speaker Affiliation
Title: -
Abstract: -
07.12. Speaker Affiliation
Title: -
Abstract: -