Benjamin Rossman, University of Toronto - Lauréat 2018 du Prix André-Aisenstadt

The complexity of detecting cliques and cycles in random graphs

A strong form of the P ≠ NP conjecture holds that no algorithm faster than n^{O(k)} solves the k-clique problem with high probability when the input is an Erdös–Rényi random graph with an appropriate edge density. Toward this conjecture, I will describe a line of work lower-bounding the average-case complexity of k-clique (and other subgraph isomorphism problems) in weak models of computation: namely, restricted classes of boolean circuits and formulas. Along the way I will discuss some of the history and current frontiers in Circuit Complexity.

Joint work with Ken-ichi Kawarabayashi, Yuan Li and Alexander Razborov.