Quebec Mathematical Sciences Colloquium

November 2, 2018 from 16:00 to 17:00 (Montreal/Miami time)

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 booleancircuits 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.

Address

CRM, Université de Montréal, Pavillon André-Aisenstadt, salle 1355
Register