2024/04/17 by Haviv, Ishay, Parnas, Michal · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2404.11504
A set family \cal F is called intersecting if every two members of \cal F intersect, and it is called uniform if all members of \cal F share a common size. A uniform family \cal F ⊆ \binom[n]k of k-subsets of [n] is ε-far from intersecting if one has to remove more than ε ⋅ \binomnk of the sets of \cal F to make it intersecting. We study the property testing problem that given query access to a uniform family \cal F ⊆ \binom[n]k, asks to distinguish between the case that \cal F is intersecting and the case that it is ε-far from intersecting. We prove that for every fixed integer r, the problem admits a non-adaptive two-sided error tester with query complexity O((ln n)/(ε)) for ε ≥ Ω( ((k)/(n))r) and a non-adaptive one-sided error tester with query complexity O((ln k)/(ε)) for ε ≥ Ω( ((k2)/(n))r). The query complexities are optimal up to the logarithmic terms. For ε ≥ Ω( ((k2)/(n))2), we further provide a non-adaptive one-sided error tester with optimal query complexity of O((1)/(ε)). Our findings show that the query complexity of the problem behaves differently from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS, 2024).