Lower bounds, data structures, rigidity, circuits, and all that

A static data-structure problem is simply a function . A data structure for with word-space , word size and time is a decomposition where , , and each output bit coordinate of depends on input words. The basic case suffices for this post. For background and some pictures see e.g.˜my book [Vio23]. The lower bound […]