BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20251105T165208EST-1896EuXUEv@132.216.98.100
DTSTAMP:20251105T215208Z
DESCRIPTION:The complexity of detecting cliques and cycles in random graphs
 \n\nA 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 i
 nput is an Erdös–Rényi random graph with an appropriate edge density. Towa
 rd this conjecture\, I will describe a line of work lower-bounding the ave
 rage-case complexity of k-clique (and other subgraph isomorphism problems)
  in weak models of computation: namely\, restricted classes of boolean cir
 cuits and formulas. Along the way I will discuss some of the history and c
 urrent frontiers in Circuit Complexity.\n	\n	Joint work with Ken-ichi Kawara
 bayashi\, Yuan Li and Alexander Razborov.\n
DTSTART:20181102T200000Z
DTEND:20181102T210000Z
LOCATION:Room 1355\, CA\, Pav. André-Aisenstadt
SUMMARY:Benjamin Rossman\, University of Toronto - Lauréat 2018 du Prix And
 ré-Aisenstadt
URL:/mathstat/channels/event/benjamin-rossman-universi
 ty-toronto-laureat-2018-du-prix-andre-aisenstadt-291083
END:VEVENT
END:VCALENDAR