Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with dynamic data structures:
TR10-087 | 17th May 2010
Shachar Lovett, Ely Porat

A lower bound for dynamic approximate membership data structures

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 >>>

TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

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 >>>

TR19-144 | 29th October 2019
Young Ko, Omri Weinstein

An Adaptive Step Toward the Multiphase Conjecture

Revisions: 1

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 >>>

TR19-146 | 31st October 2019
Max Bannach, Zacharias Heinrich, RĂ¼diger Reischuk, Till Tantau

Dynamic Kernels for Hitting Sets and Set Packing

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 >>>

ISSN 1433-8092 | Imprint