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 > Departmental Seminar Prof. Rahul Santhanam
More in this section Events articles

Departmental Seminar Prof. Rahul Santhanam

13/03/2018 (15:00-16:00)

Rahul Santhanam

Prof. Rahul Santhanam, University of Oxford

The Minimum Circuit Size Problem: A Survey and Recent Results

Departmental Seminar: a talk for everyone giving a good introduction to a topic.

In the Minimum Circuit Size Problem (MCSP), the input is the truth table of a Boolean function F, and a parameter s, and the output is YES iff F has circuits of size at most s. Intuitively speaking, MCSP is a problem that asks about the compressibility of strings.

MCSP is a fundamental problem that has been studied since the 1950s, and yet remains mysterious. It is easy to see that MCSP is in NP, but there is no strong evidence for MCSP being solvable in polynomial time or MCSP being NP-complete. While MCSP is hard to classify in complexity-theoretic terms, it has deep connections to many areas of computer science, including circuit complexity, learning theory, cryptography and proof theory.

I will informally survey work on MCSP, and sketch some recent results. I will try to make the talk accessible to a broad audience.


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