BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Algebraic Circuit-Based Approach to Proof Complexity - Iddo Tz
 amaret (Imperial)
DTSTART:20250311T140000Z
DTEND:20250311T150000Z
UID:TALK228868@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Proof complexity is one of the central approaches to the funda
 mental hardness problems in complexity theory. In recent years\, significa
 nt efforts have been made to bridge the gap between algebraic and proof co
 mplexity through a relatively transparent reduction from algebraic circuit
 -size lower bounds to proof-size lower bounds. In this talk\, I will discu
 ss state-of-the-art lower bounds in proof complexity that leverage the alg
 ebraic circuit-based approach\, establishing it as a new tool that also dr
 aws on ideas from existing techniques—such as feasible interpolation\, r
 andom restrictions\, width-size tradeoffs\, and lifting. I will also highl
 ight some imminent open problems and potential challenges in this directio
 n.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR