<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Helvetica;">Shuo Pang</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;">University of Copenhagen</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><img width="239" height="250" id="Picture_x0020_1" src="cid:9864E00F-0D7F-44BC-BE74-660F996F07A4" _mf_state="1" title="null" alt="image001.jpg" style="width: 2.4895in; height: 2.6041in;"><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr">October 22</span><span dir="ltr">, 202</span><span dir="ltr">4</span><span dir="ltr"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;">Location: Kent 102<o:p></o:p></span></b></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><b><i><span style="font-size: 14pt;">Title:</span></i></b><span style="font-size: 11pt;"> </span><span style="font-size: 12pt;">Supercritical Tradeoffs and Tight Lifting<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 14pt;">Abstract:</span></i></b><span style="font-size: 11pt;"> </span><span style="font-size: 12pt;">In computational complexity, tradeoffs between two complexity measures show that a small value for one measure implies a lower bound on the other, typically below the worst-case upper bound. However, in a supercritical tradeoff [Razborov 2016], the lower bound can exceed this upper bound.<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;">In this talk, we present the first resolution width vs. depth tradeoff that is supercritical with respect to formula size and exhibits robustness. The formula is constructed using a compression technique introduced by [Grohe et al. 2023] in the context of Weisfeiler-Leman algorithms, and our result resolves two open problems from their work. We then present several lifting theorems that yield further supercritical tradeoffs in proof and circuit complexity, including:<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;">- Width vs. size for treelike resolution, answering a question from [Razborov 2016].<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;">- Size vs. depth for resolution, cutting planes, monotone circuits, and monotone real circuits. For instance, we show an $N$-variate function computed by a monotone circuit of size $s=poly(N)$, such that any monotone real circuit computing it within size $s^{1.5}$ must have depth at least $N^{1.9}$.<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;">The lifting theorems are new, general, and tight, which may hold broader independent interest.<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;">Joint work with S. DeRezende, N. Fleming, D. Janett, and J. Nordström.</span></p><div dir="ltr"></div></body></html>