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

  Browse A-Z

Log in

Cambridge users (raven)details Other usersdetails No account?details

Information on

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

Proof complexity of circuit lower bounds

Add to your list(s) 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

History of science for mathmos The Cambridge Trust for New Thinking in Economics Pragmatics Reading Group

Other talks

EU LIFE Lecture - "Histone Chaperones Maintain Cell Fates and Antagonize Reprogramming in C. elegans and Human Cells" Changing languages in European Higher Education: from official policies to unofficial classroom practices CANCELLED Ñande reko: alterity and (non-)participatory research with guaraní women in Bolivia Polynomial approximation of high-dimensional functions on irregular domains Centriole Duplication: from body coordination in flies to skin cell biology and cancer Genes against beans: favism, malaria and nationalism in the Middle East The role of the oculomotor system in visual attention and visual short-term memory The Anne McLaren Lecture: CRISPR-Cas Gene Editing: Biology, Technology and Ethics The frequency of ‘America’ in America 'Politics in Uncertain Times: What will the world look like in 2050 and how do you know? 'Ways of Reading, Looking, and Imagining: Contemporary Fiction and Its Optics' Oncological Imaging: introduction and non-radionuclide techniques & radionuclide techniques
 

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