PhD Seminar • Algorithms and Complexity • Testing Graph Properties with the Container Method

Please note: This PhD seminar will take place in M3 4206 and online.

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

Supervisor: Professor Eric Blais

We establish nearly optimal sample complexity bounds for testing the clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on n vertices that have a clique of size rho n from graphs for which at least epsilon n^2 edges must be added to form a rho n clique by sampling and inspecting a random subgraph on only O(rho^3/epsilon^2) vertices.

The new bounds for testing the clique property are obtained via a new extension of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.

This is joint work with Eric Blais.

To attend this PhD seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/92817301692.