Skip to main content

Seminar by Dr. Stefan Dantchev

Seminar by Dr. Stefan Dantchev

  • Date 27 Nov 2018
  • Time 2.00pm – 3.00pm, BLT2
  • Category Seminar

Resolution and the binary encoding of combinatorial principles

Location: Bourne LT2
Abstract

We investigate the size of refutations in Res(k), an extension of Resolution working on k-DNFs instead of clauses, for certain contradictions given in the less usual binary encoding. In particular, we prove lower bounds for binary k-Clique principle as well as for the Weak Pigeon-Hole Principle. Previously, a resolution lower bound was known for the former while the later was considered in the more usual unary encoding only. This is based on a joint work with Nicola Galesi (La Sapienza, Roma) and Barnaby Martin (Durham). The first half of the talk will be a kind of general introduction to Propositional Proof Complexity, and thus accessible to everyone.

Bio

Stefan Dantchev got his PhD from Aarhus University, Denmark in 2002. He spent two years at University of Leicester, before moving to Durham University. His research interests are in Computational Complexity, and in particular in Propositional Proof Complexity. 

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones.

Heading to university is exciting. Finding the right place to live will get you off to a good start.

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help.

Discover more about our academic departments and schools.

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’.

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway.

Discover more about who we are today, and our vision for the future.

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today.

We’ve played a role in thousands of careers, some of them particularly remarkable.

Find about our decision-making processes and the people who lead and manage Royal Holloway today.