Hong-Zhi Wang

Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching

We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed $\beta\ge1$ and $\delta\in(0,1)$, we exclude $O(N^\beta)$ preprocessing together with $O(N^{1-\delta})$ worst-case query time on domains containing the reduction's polylogarit...