Colloque des sciences mathématiques du Québec

2 novembre 2018 de 16 h 00 à 17 h 00 (heure de Montréal/HNE)

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.


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