3 papers
cs.DS2026
Locally Approximating the Top Eigenvector of Bounded Entry Matrices
Nicolas Menand, Erik Waingarten
We provide a local computation algorithm to approximate the top eigenvector of a symmetric matrix with entries between and…
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.DS2025
Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
Nicolas Menand, Erik Waingarten
Given a set of vectors , the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Eucl…