Testing Monotonicity of Distributions Over High-Dimensional Posets

          @misc{ scivideos_16857,
            doi = {},
            url = {https://simons.berkeley.edu/talks/testing-monotonicity-distributions-over-high-dimensional-posets},
            author = {},
            keywords = {},
            language = {en},
            title = {Testing Monotonicity of Distributions Over High-Dimensional Posets},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16857 see, \url{https://scivideos.org/index.php/Simons-Institute/16857}}
          }
          

Abstract

In this talk, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is monotone if, for any pair of domain elements x and y such that x \preceq y, p(x) \leq p(y). I am going to present the proof sketch of achieving a lower bound for this problem over a few posets, e.g., matchings, and hypercubes. The main idea of these lower bounds is the following: we introduce a new property called *bigness* over a finite domain, where the distribution is T-big if the minimum probability for any domain element is at least T. Relying on the framework of [Wu-Yang'15], we establish a lower bound of \Omega(n/\log n) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give \Omega(n/\log{n}) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. Although finding a tight upper bound for testing monotonicity remains open, I will also discuss the steps we took towards the upper bound as well. Joint work with: Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee.