Logic Seminar - Raheleh Jalali
| Dates: | 28 October 2026 |
|---|
| Times: | 15:00 - 15:00 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Current University students |
|---|
|
Speaker: Raheleh Jalali (University of Bath)
Title: The Power of Structural Rules: Proof-Size Lower Bounds for Linear Logics
Abstract: Proving non-trivial lower bounds on proof size in the classical sequent calculus remains a longstanding open problem in proof complexity. In this work, we revisit this problem through the lens of substructural and linear logics. By considering calculi that restrict contraction or weakening, we obtain systems in which derivations are subject to resource-sensitive constraints. Within these frameworks, we exhibit formulas that, while admitting short classical proofs, require substantially larger derivations. These results provide a proof-theoretic explanation of why classical systems are difficult to analyze: their efficiency stems from the interaction of structural rules, a feature that becomes visible only when examined against substructural baselines.
Travel and Contact Information
Find event
Frank Adams 1
Alan Turing Building
Manchester
