Erik Waingarten

activity

20172022

most citedLearning and Testing Junta Distributions with Subcube Conditioning

6 citations · 16 across the 9 of their papers we have counts for

collaborators

12 papers

cs.DS2021

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 $n$ -point set $X \subset {1, 2, \dots, Δ}^{d}$ , and com…

cs.DS2020★ 6 cited

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 ${- 1, 1}^{n}$ with respect to the uniform distribution, where a distribution $p$ is a $k$ -junta if its probabili…

cs.DS2019

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 $2 \leq k \in N$ and $ε > 0$ , consider the problem of findi…

cs.DS2019

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 ${- 1, 1}^{n}$ , which makes $O ~ (n / ε^{2})$ queries to a subcube condition…

cs.DS2019

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 $f : {0, 1}^{n} \to {0, 1}$ which is $α$ -far from monotone, makes poly $(n, 1/ α)$ queries and returns an est…

cs.DS2019★ 4 cited

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 $k \in N$ and $ε > 0$ , we show that the n…