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.
200 University Avenue West
Waterloo, ON N2L 3G1
Canada