Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI (Research Project)

  • Funding organization: Vienna Science and Technology Fund (WWTF)
  • Call: Information and Communication Technologies (ICT- 19)
  • Project number: ICT19-065 (Reveal-AI)

 

Project Team

Topic

At the core of several critical areas of AI and reasoning are hard-to-solve computational problems, such as the processing of constraints, carrying out sound reasoning tasks, and the verification of the correctness of procedures and protocols. All these problems are in general intractable and pose a challenge to algorithm design, even more as today’s applications demand more extensive problem inputs be solved. This requires new and more robust algorithms to facilitate further progress in technological innovation. Fortunately, typical problem inputs tend to contain some form of hidden structure, as the problem data is usually the product of a process. This research project is about revealing this hidden structure and utilizing it for an efficient solution.

Publications

19 results
2021
[19]Turbocharging Treewidth-Bounded Bayesian Network Structure Learning
,
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
Note: to appear
[bibtex]
[18]SAT-based Decision Tree Learning for Large Data Sets
,
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
Note: to appear
[bibtex]
[17]Parameterized Complexity of Small Decision Tree Learning
,
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
Note: to appear
[bibtex]
[16]The Parameterized Complexity of Clustering Incomplete Data
, , , ,
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
Note: to appear
[bibtex]
2020
[15]Complexity of abstract argumentation under a claim-centric view
,
Artificial Intelligence, volume 285, 2020.
[bibtex] [doi]
[14]On Existential MSO and its Relation to ETH
, , ,
ACM Transactions on Computation Theory, volume 12, number 4, pages 22:1–22:32, 2020.
[bibtex]
[13]MaxSAT-Based Postprocessing for Treedepth
,
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis, ed.), volume 12333 of Lecture Notes in Computer Science, pages 478–495, 2020, Springer Verlag.
[bibtex] [pdf]
[12]A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth
,
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina, Martina Seidl, eds.), volume 12178 of Lecture Notes in Computer Science, pages 267–276, 2020, Springer Verlag.
[bibtex] [pdf]
[11]Short Q-Resolution Proofs with Homomorphisms
, ,
Proceedings of SAT 2020, The 23rd International Conference on Theory and Applications of Satisfiability Testing (Luca Pulina, Martina Seidl, eds.), volume 12178 of Lecture Notes in Computer Science, pages 412–428, 2020, Springer Verlag.
[bibtex] [pdf]
[10]Finding the Hardest Formulas for Resolution
,
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis, ed.), volume 12333 of Lecture Notes in Computer Science, pages 514–530, 2020, Springer Verlag.
Note: Best Paper Award
[bibtex] [pdf]
[9]Formalizing Graph Trail Properties in Isabelle/HOL
, ,
Intelligent Computer Mathematics - 13th International Conference, CICM 2020, Bertinoro, Italy, July 26-31, 2020, Proceedings (Christoph Benzmüller, Bruce R. Miller, eds.), volume 12236 of Lecture Notes in Computer Science, pages 190–205, 2020, Springer Verlag.
[bibtex] [pdf]
[8]Threshold Treewidth and Hypertree Width
, , ,
Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, pages 1898–1904, 2020.
[bibtex] [pdf] [doi]
[7]Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
, , ,
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 (Diego Calvanese, Esra Erdem, Michael Thielscher, eds.), pages 392–402, 2020.
[bibtex] [pdf]
[6]Breaking Symmetries with RootClique and LexTopsort
, ,
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis, ed.), volume 12333 of Lecture Notes in Computer Science, pages 286–303, 2020, Springer Verlag.
[bibtex] [pdf]
[5]A Time Leap Challenge for SAT-Solving
, ,
Proceedings of CP 2020, the 26th International Conference on Principles and Practice of Constraint Programming (Helmut Simonis, ed.), volume 12333 of Lecture Notes in Computer Science, pages 267–285, 2020, Springer Verlag.
[bibtex] [pdf]
[4]Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology
, ,
Theory and Applications of Satisfiability Testing - SAT 2020 - 23rd International Conference, Alghero, Italy, July 3-10, 2020, Proceedings (Luca Pulina, Martina Seidl, eds.), volume 12178 of Lecture Notes in Computer Science, pages 343–360, 2020, Springer Verlag.
[bibtex] [doi]
[3]Lower Bounds for QBFs of Bounded Treewidth

LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020 (Holger Hermanns and Lijun Zhang and Naoki Kobayashi and Dale Miller, ed.), pages 410–424, 2020, ACM.
[bibtex] [doi]
[2]Argumentation Semantics under a Claim-centric View: Properties, Expressiveness and Relation to SETAFs
, ,
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020 (Diego Calvanese, Esra Erdem, Michael Thielscher, eds.), pages 341–350, 2020.
[bibtex] [doi]
[1]Treewidth-Aware Quantifier Elimination and Expansion for QCSP
, ,
Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings (Helmut Simonis, ed.), pages 248–266, 2020, Springer Verlag.
[bibtex] [doi]