Towards Testing Monotonicity of Distributions Over General Posets

Wednesday, February 5, 2020 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Maryam Aliakbarpour



Building and Room Number

LIDS Lounge


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


Maryam Aliakbarpour is a Ph.D. student in the Theory of Computation Group at CSAIL, MIT. Her advisor is Prof. Ronitt Rubinfeld. In 2015, she received her M.S. degree in Electrical Engineering and Computer Science from MIT. Before coming to MIT, she earned a B.S. degree in Computer Engineering from the Sharif University of Technology. Her research interest is in Learning Theory, Differential Privacy, and Property Testing. Maryam received Neekeyfar Award by the Office of the Dean for Graduate Education at MIT in 2013. She was also awarded a silver medal in the Iranian National Olympiad in Informatics, 2008.