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.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…
cs.DS2024
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…