Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
Zemin Chao, Jianhe Cen, Hengzhao Ma +1
We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of -vertex simple graphs with failure probability at most . Nelson and Yu proved…
cs.DS2026
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
Zemin Chao, Zitong Li, Xiangyu Gao +1
We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed and , we exclude…