[Colloquium] U of C - CS Theory Seminar - October 22, 2024

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Shuo Pang
University of Copenhagen


[cid:image001.jpg at 01DB206D.BE7033B0]


Tuesday, October 22, 2024 at 3:30pm
Location: Kent 102

 Title: Supercritical Tradeoffs and Tight Lifting

Abstract: 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.

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:

- Width vs. size for treelike resolution, answering a question from [Razborov 2016].
- 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}$.

The lifting theorems are new, general, and tight, which may hold broader independent interest.

Joint work with S. DeRezende, N. Fleming, D. Janett, and J. Nordström.



Bio: 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.




Host: Alexander Razborov

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241022/7db3fa0a/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 114366 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241022/7db3fa0a/attachment-0001.jpg>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241022/7db3fa0a/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241022/7db3fa0a/attachment-0003.txt>