Papers from the Department of Computing accepted at STOC 2026

Title: The Weak Rank Principle: Lower Bounds and Applications

Authors: Michal Garlík, Svyatoslav Gryaznov (Imperial College London); Hanlin Ren (IAS, Princeton); Iddo Tzameret (Imperial College London)

Summary: This paper introduces a new mathematical principle --- rooted in linear algebra --- and uses it to prove that certain computational problems and logical statements are inherently difficult to solve or verify. The principle acts as a versatile tool, yielding results across several different models of computation.

Significance: A central goal of theoretical computer science is to prove that some problems are fundamentally hard --- that no matter how clever the algorithm or argument, certain tasks will always require enormous resources. Such "lower bound" results are notoriously difficult to establish, and new techniques for proving them are rare and valuable. This paper contributes a new one with wide applicability.

Title: Lower Bounds against the Ideal Proof System in Finite Fields

Authors: Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret (Imperial College London)

Summary: This paper studies the question of how hard it is for a computer to verify mathematical proofs. The authors prove that certain families of logical statements have no short, efficiently checkable proof — even when the most powerful currently known algebraic proof methods are used. This resolves an open problem that had been outstanding in the field for several years.

Significance: Understanding the limits of automated proof verification sits at the heart of fundamental questions in mathematics and computer science, including the famous P vs NP problem. By showing that even powerful proof systems cannot efficiently certify certain statements, this work advances our understanding of what can and cannot be proven efficiently --- and brings us closer to the boundaries of what computers can do in mathematics and beyond.