2026-08-07T18:21:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19561 2024-03-12T12:17:09Z ddc:004 open_access

Testing Intersecting and Union-Closed Families Chen, Xi De, Anindya Li, Yuhao Nadimpalli, Shivam Servedio, Rocco A. Sublinear algorithms property testing computational complexity monotonicity intersecting families union-closed families 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}ⁿ → {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 ε ≥ Ω(1/√n), any non-adaptive two-sided ε-tester for intersectingness must make 2^{Ω(n^{1/4}/√{ε})} queries. We also give a 2^{Ω(√{n log(1/ε)})}-query lower bound for non-adaptive one-sided ε-testers for intersectingness. - For ε ≥ 1/2^{Ω(n^{0.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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Anindya De and Yuhao Li and Shivam Nadimpalli and Rocco A. Servedio 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.33 urn:nbn:de:0030-drops-195610 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.33 eng https://creativecommons.org/licenses/by/4.0/legalcode