6 citations · 9 across the 4 of their papers we have counts for
6 papers · 1 filter
New Streaming Algorithms for High Dimensional EMD and MST
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an -point set , and com…
Erasure-Resilient Sublinear-Time Graph Algorithms
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input gra…
Learning and Testing Junta Distributions with Subcube Conditioning
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study the problems of learning and testing junta distributions on with respect to the uniform distribution, where a distribution is a -junta if its probabili…
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Clément L. Canonne, Xi Chen, Gautam Kamath +2
We give a nearly-optimal algorithm for testing uniformity of distributions supported on , which makes queries to a subcube condition…
Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, Erik Waingarten
We study the problem of estimating the number of edges of an unknown, undirected graph with access to an independent set oracle. When queried about a subset $S\subseteq…
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
Amit Levi, Yuichi Yoshida
We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'1…