6 citations · 9 across the 3 of their papers we have counts for
4 papers
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…
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…
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…
On the Converse of Talagrand's Influence Inequality
Saleet Klein, Amit Levi, Muli Safra +2
In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of nu…