Sandeep Silwal

Improved Frequency Estimation Algorithms with and without Predictions

2023 · arXiv (Cornell University)

Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the …

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

2025 · arXiv (Cornell University)

We study beyond worst-case dimensionality reduction for $s$-sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We first consider average-case guarantees. A folklore upper bound …