Learning and Testing Junta Distributions with Subcube Conditioning

MaRDI QIDQ6339456zbMATH OpenFDO

Authors Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

Publication date 26 April 2020

Abstract: 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 probability mass function $p(x)$ depends on a subset of at most $k$ variables. The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning [BC18, CCKLW20]. We give two applications: 1. An algorithm for learning $k$-junta distributions with $ildeO(k/epsilo{n}^2)logn+O(2^k/epsilo{n}^2)$ subcube conditioning queries, and 2. An algorithm for testing $k$-junta distributions with $ildeO((k+sqrtn)/epsilo{n}^2)$ subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour, Blais, and Rubinfeld [ABR17].

This page was built for publication: Learning and Testing Junta Distributions with Subcube Conditioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339456)