The Algebraic Circuit-Based Approach to Proof Complexity

Add to your list(s) Download to your calendar using vCal

• Iddo Tzamaret (Imperial)
• Tuesday 11 March 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

Proof complexity is one of the central approaches to the fundamental hardness problems in complexity theory. In recent years, significant efforts have been made to bridge the gap between algebraic and proof complexity through a relatively transparent reduction from algebraic circuit-size lower bounds to proof-size lower bounds. In this talk, I will discuss state-of-the-art lower bounds in proof complexity that leverage the algebraic circuit-based approach, establishing it as a new tool that also draws on ideas from existing techniques—such as feasible interpolation, random restrictions, width-size tradeoffs, and lifting. I will also highlight some imminent open problems and potential challenges in this direction.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.