Abstract

I will describe a recent work with Ishay Haviv (RANDOM 2024) which presents efficient algorithms for testing if a given k-uniform family of sets over [n] is intersecting or epsilon-far from intersecting, and of course tell stories of my many years of intersecting with Dana. We present both a tolerant testing algorithm for this problem and one sided error non-adaptive testing algorithms for various values of epsilon as a function of k and n. Our results are optimal or optimal up to logarithmic factors in n and k, and as we show the query complexity of the problem differs from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS 2024).