PhD Seminar • Algorithms and Complexity • A Tolerant Independent Set Tester

Please note: This PhD seminar will take place in DC 1302 and online.

Cameron Seth, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Eric Blais

In this talk we study a simple algorithm for tolerant testing the property of having a rho n independent set in the dense graph model. In particular, we give an algorithm that inspects a random subgraph on O(rho^3/eps^2) vertices and, with high probability, distinguishes between graphs that have an induced subgraph of size rho n with less than (eps/polylog(eps)) n^2 edges from graphs for which every induced subgraph of size rho n has at least eps n^2 edges. The notion of tolerant testing generalizes the standard notion of testing, however, our result matches the sample complexity bounds of the standard testing problem (Blais and Seth 2023, Feige, Langberg and Schechman 2004), and, surprisingly, shows that tolerant testing the independent set property is no harder than the standard testing problem.

Our main technique is the graph container method, which is a powerful tool for many problems related to counting independent sets, and that has recently seen applications in graph property testing (Blais and Seth 2023, 2024). In this talk we will give a brief introduction to the container method and discuss our main technical contribution: a new graph container lemma that applies to sparse subgraphs instead of independent sets.

To attend this PhD seminar in person, please go to DC 1302. You can also attend virtually on Zoom.