BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T205325Z
UID:Seminar-ACTO-499@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20191113T140000
DTEND:20191113T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Sebastian Wild: Entropy Trees: Range-Minimum Queries In Optimal Average-Case Space\n\nI will present some basics of succinct (=space-efficient) data structures and a recent result in the area of distribution-succinct data structures, i.e., data structures that have (asymptotically) optimal expected space usage (as opposed to only optimal worst case) for a certain data-structuring task.\n\nMore specifically, I will talk about (and define) the range-minimum query (RMQ) problem, a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal 2n+o(n) bits of space and constant query time are known, it has been unknown whether such a data structure can be made adaptive to the reduced entropy of random inputs (Davoodi et al. 2014). We construct a succinct data structure with the optimal 1.736n+o(n) bits of space on average for random RMQ instances, settling this open problem.\n\nOur solution relies on a compressed data structure for binary trees that is of independent interest. It can store a (static) binary search tree generated by random insertions in asymptotically optimal expected space and supports many queries in constant time.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=499
LOCATION:
END:VEVENT
END:VCALENDAR