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 Hubie Chen
More in this section Events articles

Seminar Hubie Chen

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

Hubie Chen

Hubie Chen, Birkbeck University of London

A Personal Perspective on SAT and CSP: Tractability, Complexity, Quantification, Proofs

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

I will give a guided, personal tour of some theoretical results on SAT, CSP, and their quantified versions. In particular, I will study the impact of the variable interactions on the complexity; here, the graph-theoretic measure of treewidth, and generalizations thereof, play a key role. In this context, I will also present results on the existence of proofs certifying unsatisfiability of problem instances. Parallels between the quantified and non-quantified cases will be highlighted, and open problems and directions will be offered. I will end with a general discussion of QBF proof systems and proof complexity.


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