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

• Wolfgang Dvorak
• Markus Hecher
• Matthias König
• Vaidyanathan P. R.
• André Schidler
• Stefan Szeider (PI)
• Stefan Woltran (co-PI)

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

33 results

2022
[33]	A SAT Approach to Twin-Width André Schidler, Stefan Szeider Proceedings of ALENEX 2022, the 24nd SIAM Symposium on Algorithm Engineering and Experiments, 2022, Society for Industrial and Applied Mathematics (SIAM). Note: to appear [bibtex] [pdf]
2021
[32]	Finding the Hardest Formulas for Resolution Tomáš Peitl, Stefan Szeider Journal Artificial Intelligence Research, volume 72, pages 69–97, 2021. Note: Conference Award Track, best paper CP 2020 [bibtex] [doi]
[31]	DynASP2.5: Dynamic Programming on Tree Decompositions in Action Johannes Klaus Fichte, Markus Hecher, Michael Morak, Stefan Woltran Algorithms, volume 14, number 3, pages 81, 2021. [bibtex] [pdf] [doi]
[30]	Learning fast-inference Bayesian networks Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider Proceedings of NeurIPS 2021, the Thirty-fifth Conference on Neural Information Processing Systems, 2021. Note: to appear [bibtex]
[29]	Turbocharging Treewidth-Bounded Bayesian Network Structure Learning Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 3895–3903, 2021, AAAI Press. [bibtex] [pdf]
[28]	Computing Optimal Hypertree Decompositions with SAT Andre Schidler, Stefan Szeider Proceeding of IJCAI-21, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou, ed.), 2021. [bibtex] [doi]
[27]	SAT-based Decision Tree Learning for Large Data Sets André Schidler, Stefan Szeider Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 3904–3912, 2021, AAAI Press. [bibtex] [pdf]
[26]	Finding the Hardest Formulas for Resolution (Extended Abstract) Tomás Peitl, Stefan Szeider Proceeding of IJCAI-21, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou, ed.), pages 4814–4818, 2021. Note: Sister Conferences Best Papers [bibtex] [doi]
[25]	Parameterized Complexity of Small Decision Tree Learning Sebastian Ordyniak, Stefan Szeider Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6454–6462, 2021, AAAI Press. [bibtex] [pdf]
[24]	Backdoor DNFs Sebastian Ordyniak, Andre Schidler, Stefan Szeider Proceeding of IJCAI-2021, the 30th International Joint Conference on Artificial Intelligence (Zhi-Hua Zhou, ed.), pages 1403–1409, 2021. [bibtex] [doi]
[23]	SAT Modulo Symmetries for Graph Generation Markus Kirchweger, Stefan Szeider Proceeings of CP 2021, the 27th International Conference on Principles and Practice of Constraint Programming (Laurent D. Michel, ed.), pages 39:1–-39:17, 2021, Dagstuhl Publishing. [bibtex] [pdf] [doi]
[22]	Treewidth-Aware Complexity in ASP: Not All Positive Cycles Are Equally Hard Markus Hecher, Jorge Fandinno Proceedings of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6312–6320, 2021. [bibtex]
[21]	Knowledge-Base Degrees of Inconsistency: Complexity and Counting Johannes Klaus Fichte, Markus Hecher, Arne Meier Proceedings of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6349–6357, 2021. [bibtex] [pdf]
[20]	The Parameterized Complexity of Clustering Incomplete Data Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 7296–7304, 2021, AAAI Press. [bibtex] [pdf]
[19]	Recursion in Abstract Argumentation is Hard — On the Complexity of Semantics Based on Weak Admissibility Wolfgang Dvorák, Markus Ulbricht, Stefan Woltran Proceedings of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6288–6295, 2021. [bibtex]
[18]	The Complexity Landscape of Claim-Augmented Argumentation Frameworks Wolfgang Dvorák, Anna Rapberger, Stefan Woltran Proceedings of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 6296–6303, 2021. [bibtex]
2020
[17]	Complexity of abstract argumentation under a claim-centric view Wolfgang Dvorák, Stefan Woltran Artificial Intelligence, volume 285, 2020. [bibtex] [doi]
[16]	On Existential MSO and its Relation to ETH Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider ACM Transactions on Computation Theory, volume 12, number 4, pages 22:1–22:32, 2020. [bibtex]
[15]	Computational Argumentation - Formal Models and Complexity Results (invited talk) Stefan Woltran Proceedings of the 35th Italian Conference on Computational Logic - CILC 2020, Rende, Italy, October 13-15, 2020 (Francesco Calimeri, Simona Perri, Ester Zumpano, eds.), volume 2710 of CEUR Workshop Proceedings, pages 2, 2020, CEUR-WS.org. [bibtex] [pdf]
[14]	MaxSAT-Based Postprocessing for Treedepth Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider 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]
[13]	A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth Friedrich Slivovsky, Stefan Szeider 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]
[12]	Short Q-Resolution Proofs with Homomorphisms Ankit Shukla, Friedrich Slivovsky, Stefan Szeider 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]
[11]	Finding the Hardest Formulas for Resolution Tomáš Peitl, Stefan Szeider 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]
[10]	Formalizing Graph Trail Properties in Isabelle/HOL Laura Kovács, Hanna Lachnitt, Stefan Szeider 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]
[9]	Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology Markus Hecher, Patrick Thier, Stefan Woltran 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]
[8]	Treewidth-aware Reductions of Normal ASP to SAT - Is Normal ASP Harder than SAT after All? Markus Hecher 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 485–495, 2020. [bibtex]
[7]	Threshold Treewidth and Hypertree Width Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider 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]
[6]	Fixed-Parameter Tractability of Dependency QBF with Structural Parameters Robert Ganian, Tomás Peitl, Friedrich Slivovsky, Stefan Szeider 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]
[5]	Breaking Symmetries with RootClique and LexTopsort Johannes K. Fichte, Markus Hecher, Stefan Szeider 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]
[4]	A Time Leap Challenge for SAT-Solving Johannes K. Fichte, Markus Hecher, Stefan Szeider 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]
[3]	Lower Bounds for QBFs of Bounded Treewidth Johannes Klaus Fichte and Markus Hecher and Andreas Pfandler 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]	Treewidth-Aware Quantifier Elimination and Expansion for QCSP Johannes Klaus Fichte, Markus Hecher, Maximilian F. I. Kieler 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]
[1]	Argumentation Semantics under a Claim-centric View: Properties, Expressiveness and Relation to SETAFs Wolfgang Dvorák, Anna Rapberger, Stefan Woltran 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]