Lower Bounds for Semi-adaptive Data Structures via Corruption

Abstrakt

We generalized a result of Ko and Weinstein [FOCS, 2020]. We proved that query time of any dynamic semi-adaptive data structure computing a function f is bounded by the corruption bound of f, provided that the data structure has sufficiently small update time.

Klíčová slova

• semi-adaptive dynamic data structure
• polynomial lower bound
• corruption bound
• information theory