Monotone probability distributions over the Boolean cube can be learned with sublinear samples A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples of an unknown monotone distribution over the Boolean cube, we give (to our knowledge) the first algorithm that learns an approximation of the distribution in statistical distance using a number of samples that is sublinear in the domain.  :68,do this, we develop a structural lemma describing monotone probability distributions. The structural lemma has further implications to the sample complexity of basic testing tasks for analyzing monotone probability distributions over the Boolean cube: We use it to give nontrivial upper bounds on the tasks of estimating the distance of a monotone distribution to uniform and of estimating the support size of a monotone distribution. In the setting of monotone probability distributions over the Boolean cube, our algorithms are the first to have sample complexity lower than known lower bounds for the same testing tasks on arbitrary (not necessarily monotone) probability distributions.  further :171,consequence of our learning algorithm is an improved sample complexity for the task of testing whether a distribution on the Boolean cube is monotone.

Approximating the noise sensitivity of a monotone Boolean function The noise sensitivity of a Boolean function f: 0,1n rightarrow 0,1 is one of its fundamental properties. A function of a positive noise parameter delta, it is denoted as NS_deltaf. Here we study the algorithmic problem of approximating it for monotone f, such that NS_deltaf geq 1nC for constant C, and where delta satisfies 1n leq delta leq 12. For such f and delta, we give a randomized algorithm performing Oleft(fracmin(1,sqrtn delta log1.5 n) NS_deltaf textpolyleft(frac1epsilonright)right) queries and approximating NS_deltaf to within a multiplicative factor of (1pm epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omegaleft(fracmin(1,sqrtn delta)NS_deltaf cdot nxiright) on the query complexity of any algorithm that approximates NS_deltaf to within any constant factor, where xi can be any positive constant. Thus, our algorithmu0027s query complexity is close to optimal in terms of its dependence on n.  :145,introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of thin functions with certain properties. The existence of such thin functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.