Shachar Lovett, Ely Porat

An approximate membership data structure is a randomized data

structure for representing a set which supports membership

queries. It allows for a small false positive error rate but has

no false negative errors. Such data structures were first

introduced by Bloom in the 1970's, and have since had numerous

applications, ...
more >>>

Joe Boninger, Joshua Brody, Owen Kephart

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

Young Ko, Omri Weinstein

In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving $polynomial$ lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make $n^\epsilon$ cell-probes in either the update or query phase, ... more >>>

Max Bannach, Zacharias Heinrich, RĂ¼diger Reischuk, Till Tantau

Computing kernels for the hitting set problem (the problem of

finding a size-$k$ set that intersects each hyperedge of a

hypergraph) is a well-studied computational problem. For hypergraphs

with $m$ hyperedges, each of size at most~$d$, the best algorithms

can compute kernels of size $O(k^d)$ in ...
more >>>