<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Aptos",sans-serif"> </span><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Shuo Pang</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">University of Copenhagen</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><img width="239" height="250" style="width:2.4895in;height:2.6041in" id="Picture_x0020_1" src="cid:image001.jpg@01DB206D.BE7033B0"><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, </span>
</b><b><span style="font-size:11.0pt">October 22<span style="color:black">, 202</span>4<span style="color:black"> at 3:30pm</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt">Location: Kent 102</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><b><i><span style="font-size:14.0pt">Title:</span></i></b><span style="font-size:11.0pt">
</span><span style="font-size:12.0pt">Supercritical Tradeoffs and Tight Lifting</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:14.0pt">Abstract:</span></i></b><span style="font-size:11.0pt">
</span><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt">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:
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt">- Width vs. size for treelike resolution, answering a question from [Razborov 2016].</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt">- 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}$.
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt">The lifting theorems are new, general, and tight, which may hold broader independent interest.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt">Joint work with S. DeRezende, N. Fleming, D. Janett, and J. Nordström.</span><o:p></o:p></p>
<p><span style="color:black"> </span><o:p></o:p></p>
<p><b><i><span style="font-size:14.0pt">Bio:</span></i></b><span style="font-size:11.0pt">
</span>Shuo Pang is a postdoc in computer science at the University of Copenhagen, funded by the EU Horizon MSCA postdoctoral fellowship. He received his PhD in mathematics from the University of Chicago in 2022 under the supervision of Alexander Razborov.
His research is in computational complexity and discrete mathematics, particularly proof complexity.<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p> <o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> A</span></span></b><span class="apple-converted-space"><b><span style="font-family:Helvetica">lexander Razborov</span></b></span><br>
<br>
<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>