[Theory] Theory talk tomorrow: Yassine Ghannane

[Aaron Potechin via Theory]

Hi everyone,

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.

Again, Yassine's title and abstract are below.

Best,
Aaron


Title : Polynomial calculus over non-Boolean bases


Abstract : In a recent breakthrough, Sokolov [Sok'20] proved the first lower bounds for polynomial calculus over the {± 1} 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 :


1) FPHP over {± 1}: We prove exponential size lower bounds for the functional pigeonhole principle over the {± 1} basis, answering an open problem posed in [Sok'20].


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.


3) Automatability : We show size non-automatability of polynomial calculus over {0,1} and {± 1} variables simultaneously.


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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250508/b14e616d/attachment.html>