New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions

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. Using this technique we obtain new lower bounds for monotonicity testing over discrete cubes and tight lower bounds for log...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-07
Main Authors: Cheng, Yuqian, Kane, Daniel M, Zheng, Zhicheng
Format: Article
Language:English
Subjects:
Concavity
Cubes
Inequalities
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. Using this technique we obtain new lower bounds for monotonicity testing over discrete cubes and tight lower bounds for log-concavity testing. Our basic technique involves constructing a pair of moment-matching families of distributions by tweaking the probabilities of pairs of bins so that one family maintains the defining inequalities while the other violates them.
ISSN:2331-8422