University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > The Algebraic Circuit-Based Approach to Proof Complexity

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

The Algebraic Circuit-Based Approach to Proof Complexity

Download to your calendar using vCal

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:

Note that ex-directory lists are not shown.

Other lists

Department of Plant Sciences, Seminar Room Average on Sundays: 7463.60714286 kWh https://cl-cam-ac-uk.zoom.us/j/4361570789?pwd=Nkl2T3ZLaTZwRm05bzRTOUUxY3Q4QT09&from=addon

Other talks

Group Work Topic Film, TV shows for Medical Education, ‘The Wire’ as a case study Differences between Robin and Neumann eigenvalues A flexible Monte Carlo quantitative bias analysis for unmeasured confounding Peri-Operative Medicine, and Obstetrics and Gynaecology Title to be confirmed: ANUBIS
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity