{"id":"arxiv/2601.22393","url":"https://arxiv.org/abs/2601.22393","tags":["cs.LO","cs.CC","math.LO"],"score":0,"title":"Proof Complexity of Linear Logics","domain":"cs.LO","source":"arxiv","authors":["Amirhossein Akbar Tabatabai","Raheleh Jalali"],"reviews":0,"subject":"cs.LO","summary":"Proving proof-size lower bounds for $\\mathbf{LK}$, the sequent calculus for classical propositional logic, remains one of the major open problems in proof complexity. We shed new light on this challenge by isolating the power of structural rules and showing that their combination is dramatically stronger than any individual structural rule alone, even in the presence of the controlled structural rules provided by linear exponentials. It is easy to see that $\\mathbf{LK}$ without the weakening rule is significantly weaker than $\\mathbf{LK}$ with respect to proof complexity. It therefore…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-29","reactions":{}}