Event

Lecture by Benjamin Rossman, 2018 André-Aisenstadt Prize Recipient

Friday, November 2, 2018 16:00to17:00
Room 1355, Pav. André-Aisenstadt, CA

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ö–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. Une réception suivra la conférence au Salon Maurice-L’Abbé (salle 6245). A reception will follow at Salon Maurice-L’Abbé (Room 6245).

BIOGRAPHY

Ben Rossman received his PhD in 2010 at MIT under Madhu Sudan, and held postdocs at the Tokyo Institute of Technology, the Simons Institute for the Theory of Computing at Berkeley, and the National Institute of Informatics in Tokyo before joining the University of Toronto in 2016. He is a Sloan Fellow (2017) and an invited speaker at the International Congress of Mathematicians in Rio de Janeiro (2018).

Ben works in computational complexity theory, a branch of theoretical computer science that classifies problems according to their relative difficulty. His research seeks to quantify the minimum resources required to solve basic problems in combinatorial models such as Boolean circuits. Through creative techniques based in logic and the probabilistic method, Ben has derived groundbreaking lower bounds on the complexity of detecting cliques and determining connectivity in random graphs. His other notable results include size and depth hierarchy theorems for bounded-depth circuits, answering longstanding questions. This work has contributed to a reemergence of interest in circuit complexity, a concrete approach to P vs NP which had seen little progress since breakthroughs of the 1980’s. In fall 2018, Ben will be coorganizing a special semester on this topic at the Simons Institute.

Follow us on

Back to top