Testing Intersecting and Union-Closed Families.
X. Chen and A. De and Y. Li and S. Nadimpalli and R. Servedio.
15th Innovations in Theoretical Computer Science Conference (ITCS), 2024.

Abstract:

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 \emph{intersecting} families and \emph{union-closed} families. A function $f:\{0,1\}^n \to \{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:

  • For $\eps \geq \Omega(1/\sqrt{n})$, any non-adaptive two-sided $\eps$-tester for intersectingness must make $2^{\Omega(n^{1/4}/\sqrt{\eps})}$ queries. We also give a $2^{\Omega(\sqrt{n \log(1/\eps)})}$-query lower bound for non-adaptive one-sided $\eps$-testers for intersectingness.

  • For $\eps \geq 1/2^{\Omega(n^{0.49})}$, any non-adaptive two-sided $\eps$-tester for union-closedness must make $n^{\Omega(\log(1/\eps))}$ queries.

    • Thus, neither intersectingness nor union-closedness shares the $\poly(n,1/\eps)$-query non-adaptive testability that is enjoyed by monotonicity.

    To complement our lower bounds, we also give a simple $\poly(n^{\sqrt{n\log(1/\eps)}},1/\eps)$-query, one-sided, non-adaptive algorithm for $\eps$-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 $\eps = \Theta(1/\sqrt{n})$, and for one-sided testing of intersectingness when $\eps=\Theta(1).$

    pdf of full version on arxiv

    Back to main papers page