New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions

Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng

We develop a new technique for proving distribution testing lower bounds for properties defined by inequalities involving the bin probabilities of the distribution in question. Usi…