Amit Levi

activity

20152021

most citedLearning and Testing Junta Distributions with Subcube Conditioning

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

collaborators

Showing 2019Show all

3 papers · 1 filter

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.CC2019

Hard properties with (very) short PCPPs and their applications

Omri Ben-Eliezer, Eldar Fischer, Amit Levi +1

We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed $ℓ$ , w…

cs.DS2019★ 3 cited

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 $G = ([n], E)$ with access to an independent set oracle. When queried about a subset $S\subseteq…