Heribert Vollmer

Nadia Creignou

Phokion G. Kolaitis

Nowadays constraint satisfaction problems (CSPs) are ubiquitous in many different areas of computer science, from artificial intelligence and database systems to circuit design, network optimization, and theory of programming languages. Consequently, it is important to analyze and pinpoint the computational complexity of certain algorithmic tasks related to constraint satisfaction. The complexity-theoretic results of these tasks may have a direct impact on, for instance, the design and processing of database query languages, or strategies in data-mining, or the design and implementation of planners. This state-of-the-art survey contains the papers that were invited by the organizers after conclusion of an International Dagstuhl-Seminar on Complexity of Constraints, held in Dagstuhl Castle, Germany, in October 2006. A number of speakers were solicited to write surveys presenting the state of the art in their area of expertise. These contributions were peer-reviewed by experts in the field and revised before they were collated to the 9 papers of this volume. In addition, the volume contains a reprint of a survey by Kolaitis and Vardi on the logical approach to constraint satisfaction that first appeared in 'Finite Model Theory and its Applications', published by Springer in 2007.

An Overview of Current Research Themes

Complexity of Constraints

An advanced textbook giving a broad, modern view of the computational complexity theory of boolean circuits, with extensive references, for theoretical computer scientists and mathematicians.

A Uniform Approach

Introduction to Circuit Complexity

Berthold Vöcking

Helmut Alt

Martin Dietzfelbinger

Rüdiger Reischuk

Christian Scheideler

Dorothea Wagner

Hinter vielen Computer-Programmen stecken intelligente Verfahren, die man als Algorithmen bezeichnet. Algorithmen lösen nicht nur mathematische Zahlen-Aufgaben, sondern auch ganz alltägliche Probleme: Wie ermittle ich den kürzesten Weg zwischen zwei Orten? Oder, wie kann ich einen Kuchen gerecht aufteilen? In diesem Buch erklären Informatiker 43 besonders elegante Algorithmen und illustrieren die Grundprinzipien des Algorithmendesigns anhand von interessanten Anwendungen, ohne dabei vom Leser spezielle Vorkenntnisse zu erwarten.

Taschenbuch der Algorithmen

Jouko Väänänen

Samson Abramsky

Juha Kontinen

In this volume, different aspects of logics for dependence and independence are discussed, including both the logical and computational aspects of dependence logic, and also applications in a number of areas, such as statistics, social choice theory, databases, and computer security. The contributing authors represent leading experts in this relatively new field, each of whom was invited to write a chapter based on talks given at seminars held at the Schloss Dagstuhl Leibniz Center for Informatics in Wadern, Germany (in February 2013 and June 2015) and an Academy Colloquium at the Royal Netherlands Academy of Arts and Sciences (March 2014). Altogether, these chapters provide the most up-to-date look at this developing and highly interdisciplinary field and will be of interest to a broad group of logicians, mathematicians, statisticians, philosophers, and scientists. Topics covered include a comprehensive survey of many propositional, modal, and first-order variants of dependence logic; new results concerning expressive power of several variants of dependence logic with different sets of logical connectives and generalized dependence atoms; connections between inclusion logic and the least-fixed point logic; an overview of dependencies in databases by addressing the relationships between implication problems for fragments of statistical conditional independencies, embedded multivalued dependencies, and propositional logic; various Markovian models used to characterize dependencies and causality among variables in multivariate systems; applications of dependence logic in social choice theory; and an introduction to the theory of secret sharing, pointing out connections to dependence and independence logic.

Theory and Applications

Dependence Logic

Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas – they facilitate new applications in science, medicine, production, logistics, traffic, communi¬cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs – for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity – the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.

Algorithms Unplugged

Heribert Vollmer

About

Books

Join the club