2023/11/18 by Chen, Xi, De, Anindya, Li, Yuhao +2 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.11119
Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically intersecting families and union-closed families. A function f: \0,1\n → \0,1\ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of [n]. Our main results are that -- in sharp contrast with the property of being a monotone set system -- the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: \bullet For ε≥ Ω(1/√(n)), any non-adaptive two-sided ε-tester for intersectingness must make 2^Ω(n1/4/√ε) queries. We also give a 2Ω(√(n log(1/ε)))-query lower bound for non-adaptive one-sided ε-testers for intersectingness. \bullet For ε≥ 1/2^Ω(n0.49), any non-adaptive two-sided ε-tester for union-closedness must make nΩ(log(1/ε)) queries. Thus, neither intersectingness nor union-closedness shares the poly(n,1/ε)-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple poly(n√(nlog(1/ε)),1/ε)-query, one-sided, non-adaptive algorithm for ε-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when ε= Θ(1/√(n)), and for one-sided testing of intersectingness when ε=Θ(1).