48 citations · 79 across the 36 of their papers we have counts for
7 papers · 1 filter
Optimal Adaptive Detection of Monotone Patterns
Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed and , consider the problem of findi…
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…
Approximating the Distance to Monotonicity of Boolean Functions
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
We design a nonadaptive algorithm that, given oracle access to a function which is -far from monotone, makes poly queries and returns an est…
Finding monotone patterns in sublinear time
Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter +1
We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed and , we show that the n…
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…
Testing Unateness Nearly Optimally
Xi Chen, Erik Waingarten
We present an -query algorithm that tests whether an unknown Boolean function is unate (i.e., every variable is either…
On Mean Estimation for General Norms with Statistical Queries
Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn +1
We study the problem of mean estimation for high-dimensional distributions, assuming access to a statistical query oracle for the distribution. For a normed space $X = (\mathbb{R}^…