Project Outline

Reasoning, to derive conclusions from facts, is a fundamental task in Artificial Intelligence that arises in a wide range of applications from Robotics to Expert Systems. Different applications require different forms of reasoning such as Nonmonotonic Reasoning (e.g., reasoning under the presence of default as- sumptions), Constraint-Based Reasoning (reasoning with forbidden configurations), and Bayesian Reasoning (reasoning with uncertain data). All these forms of reasoning give rise to computational problems that can be solved algorithmically. The efficiency of algorithms has a direct impact on applications; for example, improved algorithms for Bayesian inference yield more accurate computer assisted medical diagnosis.

The aim of this project is to devise new efficient algorithms for reasoning problems and to gain new theoretical insights into the question of what makes a reasoning problem hard, and what makes it easy. We study reasoning problems within the framework of Parameterized Complexity, a new and rapidly emerging field of Algorithms and Complexity. Parameterized Complexity takes structural aspects of problem instances into account which are most significant for empirically observed problem-hardness. Most of the considered reasoning problems are intractable in general, but the real-world context of their origin provides structural information that can be made accessible to algorithms in form of parameters. This makes Parameterized Complexity an ideal setting for the analysis and efficient solution of these problems that we want to explore.

Two inputs for a reasoning problem: random (left) and realistic (right).

An Illustration: the picture to the right shows the visualizations of two inputs for a reasoning problem. The input to the left is a random input. The input to the right is a real-world input (from multiplier verification). Both inputs have approximately the same size in bits, however, evidently the real-world instance is somehow "structured", whereas the random instance is not. The parameterized complexity approach allows to utilize this kind of structure to solve the problem efficiently.

Project Record

Project Title: The Parameterized Complexity of Reasoning Problems
Principle Investigator: Stefan Szeider
Funding Organization: European Research Council (ERC)
Project Type: ERC Starting Independent Researcher Grant
Project Volume: Eur 1.4 Mio
Project Duration: Jan 2010 - Dec 2014
Host Institution: Vienna University of Technology

Project Team

Yue Chen, PhD student
Johannes Fichte, PhD student
Serge Gaspers, post-doc researcher
Sebastian Ordyniak, post-doc researcher
Friedrich Slivovsky, PhD student
Stefan Szeider, project leader

Publications

Project publications are available under open access as required by the ERC. For each publication we provide a link to a free copy, either to the publisher's web site, or to a repository with a self-archived copy of the paper. We provide this link immediately or within a few months after publication.

Inside the ERC building in Brussels.

2012

2011

  • A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. J. Computer and System Sciences, vol. 77, no. 2, pp. 422-429, 2011.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-04]
  • Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. ACM Transactions on Computational Logic, vol. 12, no. 2, article 12, 2011.
    [open access at publisher's web site]
  • The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Discrete Optimization, vol. 8, pp. 139-145, 2011.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-05]
  • Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. Artificial Intelligence, vol. 175, pp. 1722-1736, 2011.
    [open access via the AIJ Editorial Website]
  • Satisfiability of Acyclic and Almost Acyclic CNF Formulas (II). Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of SAT 2011, Fourteenth International Conference on Theory and Applications of Satisfiability Testing June 19-22, 2011, Ann Arbor, USA. Lecture Notes in Computer Science vol. 6695, pp. 47-60, Springer, 2011.
    [open access of author's self-archived copy at arxiv.org]
  • Kernels for Global Constraints. Serge Gaspers and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 540-545, 2011.
    [open access at publisher's web site]
  • Augmenting Tractable Fragments of Abstract Argumentation. Sebastian Ordyniak and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 1033-1038, 2011.
    [open access at publisher's web site]
  • Backdoors to Tractable Answer-Set Programming. Johannes Klaus Fichte and Stefan Szeider. Proceedings of IJCAI 2011, the International Joint Conference on Artificial Intelligence, AAAI Press/IJCAI, pp. 863-868, 2011.
    [open access at publisher's web site]
  • Limits of Preprocessing. Stefan Szeider. Proceedings of AAAI 2011, the Twenty-Fifth Conference on Artificial Intelligence, pp. 93-98, AAAI Press, Menlo Park, California, 2011.
    [open access at publisher's web site]
  • The Parameterized Complexity of Local Consistency. Serge Gaspers and Stefan Szeider. Proceedings of CP 2011, Principles and Practice of Constraint Programming, 17th International Conference, pp 302-316, Lecture Notes in Computer Science vol. 6876, Springer, 2011.
    [open access of author's self-archived copy at ECCC]
  • Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. Albert Atserias, Johannes Klaus Fichte, Marc Thurley. Journal of Artificial Intelligence Research, vol. 40, no. 1, pp. 353-373, 2011
    [open access at publisher's website]
  • The Good, the Bad, and the Odd: Cycles in Answer-Set Programs. Johannes Klaus Fichte. Proc. of the 2011 ESSLLI Student Session (23rd European Summer School in Logic, Language, and Information), pp. 78-86, 2011.
    [open access at organizer's website]
  • Complexity of Splits Reconstruction for Low-Degree Trees. Serge Gaspers, Mathieu Liedloff, Maya J. Stein, and Karol Suchan. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), Lecture Notes in Computer Science vol. 6986, pp. 167-178, Springer 2011.
    [open access of author's self-archived copy at arxiv.org]

2010

  • Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Proceedings of SODA 2010, the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp. 511-517, SIAM, 2010.
    [open access at publisher's web site]
  • Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of FSTTCS 2010, 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), pp. 84-95, 2010.
    [open access at publisher's web site]
  • Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo. Proceedings of IPEC 2010, International Symposium on Parameterized and Exact Computation (formerly IWPEC). Lecture Notes in Computer Science, vol. 6478, pp. 158-169, 2010.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-02]
  • Parameterizing by the Number of Numbers. Michael R. Fellows, Serge Gaspers, Frances A. Rosamond. Proceedings of IPEC 2010, International Symposium on Parameterized and Exact Computation (formerly IWPEC). Lecture Notes in Computer Science, vol. 6478, pp. 123-134, 2010.
    [open access of author's self-archived copy at arxiv.org]
  • Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak and Stefan Szeider. Proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 311-322.
    [open access of author's self-archived copy at INFSYS repository, RR-1843-11-03]
  • Reasoning in Argumentation Frameworks of Bounded Clique-Width. Wolfgang Dvovrak, Stefan Szeider, and Stefan Woltran. Proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 219-230.
    [open access of author's self-archived copy at DBAI repository, TR-2011-71]
  • Algorithms and Complexity Results for Exact Bayesian Structure Learning. Sebastian Ordyniak and Stefan Szeider. Proceedings of UAI 2010, The 26th Conference on Uncertainty in Artificial Intelligence, Catalina Island, California, USA, July 8-11, 2010. Peter Grünwald and Peter Spirtes (eds.), AUAI Press, Corvallis, pp. 401-408, 2010.
    [open access at conference web site]
  • Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. Reinhard Pichler, Stefan Rümmele, Stefan Szeider and Stefan Woltran. Proceedings of KR 2010, Twelfth International Conference on Principles of Knowledge Representation and Reasoning Toronto, Canada, May 9-13, 2010, AAAI Press 2010.
    [open access at publisher's web site]
  • Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Seclected and revised papers of ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India. RMS Lecture Notes Series no. 13, pp. 179-190. Ramanujan Mathematical Society, 2010
    [open access of author's self-archived copy at arxiv.org]

Events

  • We have organised the first workshop on Parameterized Complexity of Computational Reasoning, PCCR 2010, as a Satellite Workshop of MFCS & CSL 2010, Brno, Czech Republic, 28 August 2010.
  • We have organised the third Workshop on Kernelization, WorKer 2011, at Vienna University of Technology, 2-4 September 2011, Vienna, Austria.

Postdoc Positions Available

Currently there are two postdoc positions available within the ERC project COMPLEX REASON. The positions are for a duration between one and two and a half years. The review of applicants will begin immediately and continue until the positions are filled. Informal inquires by email to Stefan Szeider are welcome.
  • Postdoc Position in Algorithms & Complexity

    Requirements: The candidate should have a PhD degree in Computer Science or related area; research experience at postdoctoral level is of advantage. A successful candidate should have excellent knowledge of algorithms and complexity, preferably in the setting of parameterized complexity and fixed-parameter tractability. Strong background in graph theory, combinatorics, constraint satisfaction, satisfiability, or proof complexity is of advantage.
  • Postdoc Position in Propabilistic Reasoning

    Requirements: The candidates should have a PhD degree in Computer Science or related area; research experience at postdoctoral level is of advantage. A successful candidate will have excellent knowledge of state-of-the-art algorithms and tools for probabilistic reasoning, excellent background in algorithms and complexity, as well as experience in prototype implementation and testing. Further background in combinatorics, constraint satisfaction, or probabilistic network structure learning is of advantage.
  • How to Apply

    The candidates should send their cv, list of publications, a brief outline of previous research, the names and addresses of three referees, and the earliest possible starting date, per email to:

    Ms Eva Nedona
    email: eva "at" kr "dot" tuwien "dot" ac "dot" at
    Knowledge-Based Systems Group
    Institute of Information Systems
    Vienna University of Technology
    Favoritenstrasse 9-11
    A-1040 Vienna, Austria