BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T101905Z
UID:Seminar-NESTiD-1157@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20221027T161500
DTEND:20221027T171500
SUMMARY:Durham-Liverpool synergy Series
DESCRIPTION:Sebastian Wild: Putting your graphs on a diet: Centralized and distributed representations for classes of graphs\n\nThis talk will discuss different models for space-efficient representations of graphs and how they relate.\nThe first model is that of succinct data structures, where all data is held centrally and the emphasis is on supporting certain queries (such as adjacency, degree, neighbors, but also (unweighted) shortest-path distance) efficiently while using close to the information-theoretic minimum of space. Such representations can be used as a drop-in replacement for an adjacency-list representation. I will present some recent results on permutation graphs along these lines and introduce the building blocks of space-efficient data structures used therein.\n\nThe second model is that of graph labeling schemes, where the graph is stored in a distributed fashion: Each vertex is assigned a label so that the query under consideration (e.g. adjacency) can be answered from only seeing the labels of the involved vertices. Labeling schemes for the adjacency query are also known as implicit graph representations, which are the subject of the recently refuted, long-standing Implicit Graph Conjecture (IGC). I will summarize our recent work on randomized graph labeling schemes and its connection to the IGC.\n\nI will finally show an example where a centralized, succinct data structure uses strictly less space than any graph labeling scheme can achieve; this example thus exhibits an inherent space overhead for decentralized computation.\n\nThis talk is based on joint work with Nathaniel Harms and Viktor Zamaraev [1] and joint work with Konstantinos Tsakalidis and Viktor Zamaraev [2].\n\n[1] “Randomized Communication and Implicit Graph Representations”, STOC 2022,\nhttps://www.wild-inter.net/publications/harms-wild-zamaraev-2022\n[2] “Succinct Permutation Graphs”, Algorithmica 2022,\nhttps://www.wild-inter.net/publications/tsakalidis-wild-zamaraev-2022\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1157
LOCATION:
END:VEVENT
END:VCALENDAR