logo Web


logo Web

Events at the CRM

PDF version

2018 André Aisenstadt Recipient

CRM > Prizes > André Aisenstadt Prize > Recipient > Ben Rossman (University of Toronto)

2018 André Aisenstadt Prize in Mathematics Recipient
Ben Rossman (University of Toronto)

[ français ]

The lecture of Ben Rossman (University of Toronto) will take place on November 2, 2018 at the Pavillon André-Aisenstadt in room 1355.

Friday, November 2, 2018
Centre de recherches mathématiques
Pavillon André-Aisenstadt
Université de Montréal
Room 1355

16:00 - 17:00

Conference slideshow
Conference video


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


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.