Nearly Optimal Static Las Vegas Succinct Dictionary

Explore the concept of nearly optimal static Las Vegas succinct dictionaries in this 25-minute conference talk. Delve into the dictionary problem, membership in the Word RAM model, and Patrascu's data structure. Examine data structures with fractional length, succinct dictionary data structures, and the implications of allocating more space for bad inputs. Investigate "random-looking" inputs and the use of two data structures for each bucket. Conclude by discussing open problems in the field. For a more in-depth exploration, access the one-hour version of the talk available on YouTube.

Intro
Dictionary problem
Membership
Word RAM
Patrascu's data structure
Data structures with fractional length
Succinct dictionary data structure
More space on bad inputs
"Random-looking" inputs
Two data structures for each bucket
Open problems