Parameterized Compilation (Research Project)

Funding Organisation: The Austrian Science Funds, FWF
Project Number: FWF P26200

Project Team

Simone Bova (Postdoc, Project Coordinator)
Ronald de Haan (Doctoral Student)
Neha Lodha (Doctoral Student)
Stefan Szeider (Professor, Principal Investigator)

Topic

Knowledge compilation offers a compelling approach to coping with computationally hard problems. This line of research was initiated in the early 1990s, and since then has become a very active and progressing field.  Knowledge compilation proceeds in two phases: In the first phase the input data is compiled into a new representation, which is then used in a second phase to execute a number of individual tasks efficiently.  Ideally, one aims at a compilation that causes only a polynomial increase in space, and the classical theory of compilation offers theoretical tools to decide whether such a compilation is possible or not.  However, systematic research shows that most relevant problems are not compilable with a polynomial increase in space. Hence, the classical theory cannot provide reasonable guarantees for these problems.

The goal of this project is to overcome this limit of classical knowledge compilation by utilizing structural aspects of problem inputs (such as as tree-likeness, degree of cyclicity, or backdoor size). As the key to this goal we propose to study knowledge compilation within the framework of parameterized complexity, which has become an important and successful research direction in algorithms and complexity. Parameterized complexity provides powerful methods and tools for exploiting structural aspects of problems and is therefore ideally suited for this purpose. Using parameters we can exploit structural aspects of the input in order to support the compilation. Hence we aim at positive results in terms of upper bounds for compilation space and compilation time for problems that are not compilable in the classical sense.

Publications

2017

  1. Stefano Aguzzoli, Simone Bova, and Diego Valota. Free Weak Nilpotent Minimum Algebras. Soft Comput. 21(1): 79-95 (2017). Technical Report AC-TR-17-002, TU Wien, 2017.
  2. Simone Bova and Hubie Chen. How many variables are needed to express an existential positive query? Proceedings of ICDT, 2017. OpenProceedings.org, 2017, 9:1-9:16. Best Paper Award.
  3. Simone Bova and Fabio Mogavero. Herbrand Property: Finite Quasi-Herbrand Models and Lifting Chandra-Merlin Theorem to Quantified Conjunctive Queries. Proceedings of LICS, 2017. Technical Report AC-TR-17-017, TU Wien, 2017.
  4. Simone Bova and Stefan Szeider. Circuit Treewidth, Sentential Decision, and Query Compilation. Proceedings of PODS, 2017. Technical Report abs/1701.04626v1, CoRR, 2017.
  5. Ronald de Haan and Stefan Szeider. Parameterized Complexity Classes Beyond Para-NP. J. of Computer and System Sciences (2017). Technical Report AC-TR-17-004, TU Wien, 2017.
  6. Ronald de Haan. Complexity Results for Manipulation, Bribery and Control of the Kemeny Judgment Aggregation Procedure. Proceedings of AAMAS, 2017. Technical Report AC-TR-17-005, TU Wien, 2017.
  7. Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable Matching with Uncertain Pairwise Preferences. Proceedings of AAMAS, 2017. Technical Report AC-TR-17-006, TU Wien, 2017.
  8. Haris Aziz, Ronald de Haan, and Baharak Rastegari. Pareto Optimal Allocation under Uncertain Preferences. Proceedings of AAMAS, 2017. Technical Report AC-TR-17-007, TU Wien, 2017.
  9. Ronald de Haan and Marija Slavkovik. Complexity Results for Aggregating Judgments using Scoring or Distance-Based Procedures. Proceedings of AAMAS, 2017. Technical Report AC-TR-17-008, TU Wien, 2017.

2016

  1. Simone Bova. SDDs are Exponentially More Succinct than OBDDs. Proceedings of AAAI, 2016. Technical Report abs/1601.00501v1, CoRR, 2016.
  2. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Knowledge Compilation Meets Communication Complexity. Proceedings of IJCAI, 2016. Technical Report AC-TR-16-002, TU Wien, 2016.
  3. Simone Bova, Robert Ganian, and Stefan Szeider. Quantified Conjunctive Queries on Partially Ordered Sets. Theor. Comput. Sci. 618: 72-84 (2016). Technical Report abs/1408.4263v1, CoRR, 2014.
  4. Simone Bova, Robert Ganian, and Stefan Szeider. Model Checking Existential Logic on Partially Ordered Sets. ACM Trans. Comput. Log. 17(2): 10 (2016). Technical Report abs/1405.2891v1, CoRR, 2014.
  5. Simone Bova, Neha Lodha, Ronald de Haan, and Stefan Szeider. Positive and Negative Results for Parameterized Compilability. Technical Report AC-TR-16-003, TU Wien, 2016.
  6. Ulle Endriss, Umberto Grandi, Ronald de Haan, and Jérôme Lang. Succinctness of Languages for Judgment Aggregation. Proceedings of KR, 2016. Technical Report AC-TR-16-006, TU Wien, 2016.
  7. Ronald de Haan and Stefan Szeider. Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics. Proceedings of KR, 2016. Technical Report AC-TR-15-002, TU Wien, 2015.
  8. Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider. On Existential MSO and its Relation to ETH. Proceedings of MFCS, 2016.
  9. Haris Aziz, Peter Biro, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable Matching with Uncertain Linear Preferences. Proceedings of SAGT, 2016. Technical Report abs/1607.02917, CoRR, 2016.
  10. Ronald de Haan. Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation. Proceedings of ComSoc, 2016.
  11. Ronald de Haan. Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation. Proceedings of ECAI, 2016.

2015

  1. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. On Compiling CNFs into Structured Deterministic DNNFs. Proceedings of SAT, 2015. Technical Report AC-TR-15-006, TU Wien, 2015.
  2. Simone Bova and Hubie Chen. The Complexity of Equivalence, Entailment, and Minimization in Existential Positive Logic. J. Comput. Syst. Sci. 81(2): 443-457 (2015). Technical Report AC-TR-15-007, TU Wien, 2015.
  3. Simone Bova and Barnaby Martin. First-Order Queries on Finite Abelian Groups. Proceedings of CSL, 2015. Technical Report AC-TR-15-008, TU Wien, 2015.
  4. Simone Bova and Friedrich Slivovsky. On Compiling Structured CNFs to OBDDs. Proceedings of CSR, 2015. Technical Report abs/1411.5494v1, CoRR, 2014.
  5. Ulle Endriss, Ronald de Haan, and Stefan Szeider. Parameterized Complexity Results for Agenda Safety in Judgment Aggregation. Proceedings of AAMAS, 2015. Technical Report AC-TR-16-005, TU Wien, 2015.
  6. Ronald de Haan and Stefan Szeider. Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP. Proceedings of SOFSEM, 2015. Technical Report AC-TR-15-009, TU Wien, 2015.
  7. Ulle Endriss and Ronald de Haan. Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young. Proceedings of AAMAS, 2015. Technical Report AC-TR-15-010, TU Wien, 2015.
  8. Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. On the Subexponential-Time Complexity of CSP. JAIR, 52: 203-234 (2015).
  9. Ronald de Haan, and Jakub Szymanik. A Dichotomy Result for Ramsey Quantifiers. Proceedings of WoLLIC, 2015. Technical Report abs/1601.02258, CoRR, 2016.
  10. Ronald de Haan, Martin Kronegger, and Andreas Pfandler. Fixed-parameter Tractable Reductions to SAT for Planning. Proceedings of IJCAI 2015. Technical Report AC-TR-15-011, TU Wien, 2015.

2014

  1. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. A Strongly Exponential Separation of DNNFs from CNF Formulas. Technical Report abs/1411.1995v3, CoRR, 2014.
  2. Simone Bova and Hubie Chen. The Complexity of Width Minimization for Existential Positive Queries. Proceedings of ICDT, 2014.
  3. Simone Bova, Robert Ganian, and Stefan Szeider. Model Checking Existential Logic on Partially Ordered Sets. Proceedings of CSL-LICS, 2014. Technical Report abs/1405.2891v1, CoRR, 2014.
  4. Simone Bova, Robert Ganian, and Stefan Szeider. Quantified Conjunctive Queries on Partially Ordered Sets. Proceedings of IPEC, 2014. Technical Report abs/1408.4263v1, CoRR, 2014.
  5. Ronald de Haan and Stefan Szeider. Fixed-Parameter Tractable Reductions to SAT. Proceedings of SAT, 2014. Technical Report INFSYS RR-1843-14-04, TU Wien, 2014.
  6. Ronald de Haan and Stefan Szeider. The Parameterized Complexity of Reasoning Problems Beyond NP. Proceedings of KR, 2014. Technical Report abs/1312.1672, CoRR, 2013.
  7. Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. Subexponential Time Complexity of CSP with Global Constraints. Proceedings of CP, 2014. Technical Report INFSYS RR-1843-14-06, TU Wien, 2014.
  8. Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. Small Unsatisfiable Subsets in Constraint Satisfaction. Proceedings of ICTAI, 2014. Technical Report INFSYS RR-1843-14-05, TU Wien, 2014.

Events

kc-logoSymposium on New Frontiers in Knowledge Compilation

This symposium was organised by Pierre Marquis and Stefan Szeider and held in Vienna, Austria, June 4-6, 2015. The aim of this symposium was  to bring together researchers who work on knowledge compilation from various angles, including knowledge representation, constraints, theory of algorithms, complexity, machine learning, and databases, as well as researchers from related areas. Lectures and discussions have  put all these different approaches into context and stimulated a fruitful exchange of ideas between researchers from different fields. The symposium had over 30 participants and featured several invited and contributed talks.

More information can be found on the symposium homepage.

 

Dagstuhl Seminar on Recent Trends in Knowledge Compilation

Stimulated by the success of the Symposium in Vienna, another larger meeting on this topic was organized by Adnan Darwiche (UCLA, US),  Pierre Marquis (Artois University – Lens, FR), Dan Suciu (University of Washington – Seattle, US, and Stefan Szeider (TU Wien, AT). The seminar was held at Schloss Dagstuhl, Wadern, Germany,  September 17-22, 2017,

The seminar had over 40 participants and featured several invited and contributed talks as well as a demo session and and open problems session.

Among others, the seminar was an excellent occasion for disseminating results of the project, in terms of several talks.

A report on the seminar has been published as Dagstuhl Report (Volume 7, Issue 9, 2018).

More information can be found on the seminar homepage.