30 September 2014, Logic Tea, Ronald de Haan

Abstract

Oracles do not only appear in your favorite episodes of Greek mythology, but also in complexity theory. In complexity theory, an oracle can be seen as a kind of magical black box that gives you the answer to a very difficult question, for free. One type of oracle that is commonly considered solves the satisfiability problem of propositional logic (SAT), which is a so-called NP-complete problem. Engineering efforts over the last two decades have resulted in algorithms that can solve this problem efficiently in many (altough not all) cases. What if we can actually use these efficient SAT solvers as oracles?

The theory of bounded query complexity analyzes how many times we need to ask such an oracle for an answer in order to perform certain computational tasks. After starting with a gentle and intuitive explanation of the complexity of SAT, we will have an overview of some results from the field of bounded query complexity. We will stay down-to-earth (rather than flying high in the sky of abstract complexity theory), and look at some examples where the theory can be used as a tool to think about and develop algorithms that use SAT solvers as a subroutine.

Finally, as an application, we will see how this model can be used to analyze problems that come up in the area of judgment aggregation, in computational social choice.

For more information on this talk and future events please visit the website http://www.illc.uva.nl/logic_tea/ or contact Thomas Brochhagen (t.s.brochhagen at uva.nl), Johannes Marti (johannes.marti at gmail.com), Masa Mocnik (masa.mocnik at gmail.com) or Julian Schloder (julian.schloeder at gmail.com).