[Proof Complexity] MIAO seminar Tue May 20 at 14:00 CET with Kilian Risse: Supercritical tradeoffs for monotone circuits

[Jakob Nordström]

Dear all,

On Tuesday May 20 at 14:00 CET we will have the pleasure of listening to 
a presentation by Kilian Risse from EPFL, who will give a talk titled 
"Supercritical tradeoffs for monotone circuits". You find the abstract 
at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827 . 
Please feel free to share this information with colleagues who you think 
might be interested. We are also hoping to record the seminar and post 
on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch 
for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Tuesday May 20 at 14:00 on Zoom
*Supercritical tradeoffs for monotone circuits
*(Kilian Risse, EPFL)
/
We exhibit a monotone function computable by a monotone circuit of 
quasipolynomial size such that any monotone circuit of polynomial depth 
requires exponential size. This is the first size-depth tradeoff result 
for monotone circuits in the so-called supercritical regime. Our proof 
is based on an analogous result in proof complexity: We introduce a new 
family of unsatisfiable 3-CNF formulas (called bracket formulas) that 
admit resolution refutations of quasipolynomial size while any 
refutation of polynomial depth requires exponential size.

This is joint work with Mika Göös, Gilbert Maystre and Dmitry Sokolov to 
appear at /STOC '25./


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se