ABSTRACT. Many computational problems that arise in the context of AI and reasoning are NP-hard or even hard for the second level of the Polynomial Hierarchy. Practical instances of these problems often contain some "hidden structure" that can be utilized algorithmically. There are various ways of capturing the hidden structure in terms of parameters which in turn can be used by fixed-parameter algorithms. In order to achive fixed-parameter tractability for problems that are hard for the second level of the Polynomial Hierarchy, the parameter usually needs to be quite restrictive. For such problems, it therefore seems to be an even more compelling approach to utilize the hidden structure captured by the parameter not to solve the problem, but to reduce it to a different problem of lower complexity, say, to a problem in NP. The parameter can thus be less restrictive and so reasonably small for larger classes of inputs. Clearly such a reduction cannot be computed in polynomial time, unless the Polynomial Hierarchy collapses. However, the reduction can be fixed-parameter tractable and thus break complexity barriers between the levels of the Polynomial Hierarchy. SAT, the propositional satisability problem, is ideally suited as a target problem since by means of fixed-parameter tractable reductions to SAT one can make the spectacular solving power of today's SAT solvers applicable to problems at higher levels of the Polynomial Hierarchy. In fact, the extremely successful practical technique of Bounded Model Checking can, in retrospect, be seen as a fixed-parameter tractable reduction to SAT. Recently developed fixed-parameter tractable reductions to SAT break complexity barriers for several problems, including the main reasoning problems of disjunctive answer-set programming, problems arising in propositional abductive reasoning, and problems arising in agenda safety. There are already basic concepts and results for a hardness theory that can be used to provide evidence that certain parameterized problems do not admit fixed-parameter tractable reductions to SAT.

ABSTRACT. Generalized CP-nets (GCP-nets) allow a succinct representation of preferences over multi-attribute domains. As a consequence of their succinct representation, many GCP-net related tasks are computationally hard. Even finding the more preferable of two outcomes is PSPACE-complete. In this work, we employ the framework of (parameterized) complexity theory to achieve two goals: First, we want to gain a deeper understanding of the complexity of GCP-nets. Second, we search for efficient fixed-parameter tractable algorithms.

ABSTRACT. Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. In three cases we achieve the most desirable outcome: detection and evaluation are fpt.

ABSTRACT. A basic problem of logical inference systems is that of derivability: given a set of formulas X and a formula alpha, can alpha be derived from X using the inference rules? When the logical language is designed to express computational properties, the complexity of derivability assumes importance, and for most reasoning systems of even the propositional kind, the problem is hard. It is in this context that parameterized complexity offers hope for coping with hardness.

ABSTRACT. The third round of the Kurt Gödel Research Prize Fellowships Program, under the title: Connecting Foundations and Technology, aims at supporting young scholars in early stages of their academic careers by offering highest fellowships in history of logic, kindly supported by the John Templeton Foundation. Young scholars being less or exactly 40 years old at the time of the commencement of the Vienna Summer of Logic (July 9, 2014) will be awarded one fellowship award in the amount of EUR 100,000, in each of the following categories:

• Logical Foundations of Mathematics,
• Logical Foundations of Computer Science, and
• Logical Foundations of Artificial Intelligence

The following three Boards of Jurors were in charge of choosing the winners:

• Logical Foundations of Mathematics: Jan Krajíček, Angus Macintyre, and Dana Scott (Chair).
• Logical Foundations of Computer Science: Franz Baader, Johann Makowsky, and Wolfgang Thomas (Chair).
• Logical Foundations of Artificial Intelligence: Luigia Carlucci Aiello, Georg Gottlob (Chair), and Bernhard Nebel.

http://fellowship.logic.at/

ABSTRACT. The aim of the FLoC Olympic Games is to start a tradition in the spirit of the ancient Olympic Games, a Panhellenic sport festival held every four years in the sanctuary of Olympia in Greece, this time in the scientific community of computational logic. Every four years, as part of the Federated Logic Conference, the Games will gather together all the challenging disciplines from a variety of computational logic in the form of the solver competitions.

At the Award Ceremonies, the competition organizers will have the opportunity to present their competitions to the public and give away special prizes, the prestigious Kurt Gödel medals, to their successful competitors. This reinforces the main goal of the FLoC Olympic Games, that is, to facilitate the visibility of the competitions associated with the conferences and workshops of the Federated Logic Conference during the Vienna Summer of Logic.

This award ceremony will host the

• 3rd Confluence Competition (CoCo 2014);
• Configurable SAT Solver Challenge (CSSC 2014);
• Ninth Max-SAT Evaluation (Max-SAT 2014);
• QBF Gallery 2014; and
• SAT Competition 2014 (SAT-COMP 2014).