Testing Intersectingness of Uniform Families - How Dana and I Intersected

Explore a lecture on efficient algorithms for testing the intersectingness of k-uniform families of sets. Delve into recent work with Ishay Haviv, presented at RANDOM 2024, which introduces both tolerant testing algorithms and one-sided error non-adaptive testing algorithms for various epsilon values as functions of k and n. Examine how these results compare to optimal solutions, differing only by logarithmic factors in n and k. Contrast the query complexity of this problem with that of testing intersectingness in non-uniform families, as studied by Chen, De, Li, Nadimpalli, and Servedio at ITCS 2024. Gain insights into the speaker's personal experiences and collaborations with Dana throughout their career.

Testing Intersectingness of Uniform Families or how Dana and I intersected