<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi everyone,</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
I'd like to make a correction. Lunch afterwards will be collectively covered by the department (my apologies for the confusion, I misinterpreted some communication). We will likely go to Nella but this is flexible.</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Again, Yassine's title and abstract are below.</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Best,</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Aaron</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: black;">Title : P</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">olynomial
calculus over non-Boolean bases</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: black;"><br>
</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">Abstract : In a recent breakthrough, Sokolov [Sok'20] proved the first lower bounds
for polynomial calculus over the </span><span style="font-family: Arial, sans-serif, serif, EmojiFont; font-size: 13px; color: rgb(34, 34, 34);">{± 1}
</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">basis, which were then extended to finite domains over finite fields [IMP'23, DMM'24]. We further extend the landscape of our understanding of
polynomial calculus over non-Boolean bases in several directions :</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;"><br>
</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">1) FPHP over
</span><span style="font-family: Arial, sans-serif, serif, EmojiFont; font-size: 13px; color: rgb(34, 34, 34);">{± 1}</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">: We prove exponential size lower
bounds for the functional pigeonhole principle over the </span><span style="font-family: Arial, sans-serif, serif, EmojiFont; font-size: 13px; color: rgb(34, 34, 34);">{± 1}
</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">basis, answering an open problem posed in [Sok'20].</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;"><br>
</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">2) Coloring over roots of unity : We extend the recent average-case hardness result
for coloring [CdRN+23] to the roots of unity encoding by proving exponential size lower bounds in this setting.</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;"><br>
</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">3) Automatability : We show size non-automatability of polynomial calculus over {0,1}
and </span><span style="font-family: Arial, sans-serif, serif, EmojiFont; font-size: 13px; color: rgb(34, 34, 34);">{± 1}
</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: rgb(34, 34, 34);">variables
</span><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">simultaneously.</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;"><br>
</span></p>
<p style="margin-top: 0px; margin-bottom: 0px;" class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; color: black;">4) Polynomial calculus over {1,2} : We show that polynomial calculus over R with
domain {a,b}, when a/b is not a root of unity, can be surprisingly powerful : it can polynomially simulate bounded coefficient cutting planes.</span></p>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
</body>
</html>