We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Computer Science home > Events > Seminar Jan Pich
More in this section Events articles

Seminar Jan Pich

10/10/2017 (15:00-16:00)

Jan Pich

Jan Pich, Kurt Gödel Research Center for Mathematical Logic

Provability of weak circuit lower bounds

Proving lower bounds on the size of Boolean circuits computing explicit Boolean functions is a fundamental problem in the theory of computational complexity. In particular, it presents one of the main approaches to the separation of P and NP, and is closely related to the construction of various learning algorithms. Unfortunately, it is also known as a notoriously hard problem. This triggered the investigation of its proof complexity with a well-known discovery of the natural proofs barrier.

A systematic description of proof complexity of circuit lower bounds can be given in terms of mathematical logic. In this framework, one attempts to show that all existing circuit lower bounds are derivable in a constructive mathematical theory while at the same time no such theory is able to prove strong circuit lower bounds separating P and NP. We will describe the state of the art in this area and focus specifically on giving more constructive proofs of known circuit lower bounds including lower bounds for constant-depth circuits and monotone circuits. These proofs take place inside theories of bounded arithmetic formalizing feasible reasoning or, alternatively, in various extensions of Frege propositional proof system.


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback