"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. Speaker Affiliation
Title: -
Abstract: -
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. Speaker Affiliation
Title: -
Abstract: -
28.09. Speaker Affiliation
Title: -
Abstract: -
05.10. Speaker Affiliation
Title: -
Abstract: -
12.10. Speaker Affiliation
Title: -
Abstract: -
19.10. Speaker Affiliation
Title: -
Abstract: -
26.10. Speaker Affiliation
Title: -
Abstract: -
02.11. Speaker Affiliation
Title: -
Abstract: -
09.11. Speaker Affiliation
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: -