[Theory] UC Theory seminar: a reminder

[Alexander Razborov via Theory]

Shuo Pang
University of Copenhagen
 
 

 
 
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241021/6c262e64/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 114366 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241021/6c262e64/attachment-0001.jpg>