  We study dynamic algorithms robust to adaptive input generated from sources
with bounded capabilities, such as sparsity or limited interaction. For
example, we consider robust linear algebraic algorithms when the updates to the
input are sparse but given by an adversary with access to a query oracle. We
also study robust algorithms in the standard centralized setting, where an
adversary queries an algorithm in an adaptive manner, but the number of
interactions between the adversary and the algorithm is bounded. We first
recall a unified framework of [HKM+20, BKM+22, ACSS23] for answering $Q$
adaptive queries that incurs $\widetilde{\mathcal{O}}(\sqrt{Q})$ overhead in
space, which is roughly a quadratic improvement over the na\"{i}ve
implementation, and only incurs a logarithmic overhead in query time. Although
the general framework has diverse applications in machine learning and data
science, such as adaptive distance estimation, kernel density estimation,
linear regression, range queries, and point queries and serves as a preliminary
benchmark, we demonstrate even better algorithmic improvements for (1) reducing
the pre-processing time for adaptive distance estimation and (2) permitting an
unlimited number of adaptive queries for kernel density estimation. Finally, we
complement our theoretical results with additional empirical evaluations.
