Nathan White

activity

20242026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Approximate Nearest Neighbor in Ultra-High Dimensional $ℓ_{\infty}$

Nathan White, Tian Zhang

We study the approximate nearest neighbor problem under $ℓ_{\infty}$ in the ultra-high dimensional setting where the dimension $d$ is significantly larger than the number of point…

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 $p$ over $R^{n}$ is sparse versus far from sparse, given access to noisy evaluations of the polyn…

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…

Approximate Nearest Neighbor in Ultra-High Dimensional ℓ∞​

Testing noisy low-degree polynomials for sparsity

Average-Distortion Sketching

Approximate Nearest Neighbor in Ultra-High Dimensional $ℓ_{\infty}$