3 papers
cs.DS2025
Testing noisy low-degree polynomials for sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown low-degree polynomial over is sparse versus far from sparse, given access to noisy evaluations of the polyn…
cs.DS2025
Average-Distortion Sketching
Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3
We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…
cs.DM2024
Nearly Tight Bounds on Testing of Metric Properties
Yiqiao Bao, Sampath Kannan, Erik Waingarten
Given a non-negative matrix viewed as a set of distances between points, we consider the property testing problem of deciding if it is a metric. We also consider t…