University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Proof complexity of circuit lower bounds

  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

Proof complexity of circuit lower bounds

Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani .

Semantics and Syntax: A Legacy of Alan Turing

Techniques that could resolve P vs. NP are considerably restricted by well-known barriers in computational complexity. There are several corresponding results in logic stating that certain fragments of arithmetic are not sufficiently strong to prove that P differs from NP or some similar conjectures. We investigate possible extensions of these barriers to stronger theories. Mainly, Razborov’s conjecture about hardness of Nisan-Wigderson generators for Extended Frege systems and natural proofs in proof systems admitting feasible disjunction property pointed out by Rudich.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Room Three, Mill Lane Lecture Rooms, 8 Mill Lane, Cambridge. Webinar & FW11, Computer Laboratory, William Gates Building. Virtually, at Zoom

Other talks

Argentina 2005 Tea and Coffee Break TBC The physics of decision: how competitive systems compute, route, and remember The Inaccessible Game Loke CTR Seminar Series - Vincent Pasque
 

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