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

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

5 results

2020
[5]	Complexity of abstract argumentation under a claim-centric view Wolfgang Dvo\vrák, Stefan Woltran Artificial Intelligence, volume 285, 2020. [bibtex] [pdf] [doi]
[4]	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.), 2020, Springer Verlag. Note: to appear [bibtex] [pdf]
[3]	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.), 2020, Springer Verlag. Note: to appear [bibtex] [pdf]
[2]	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, 2020. Note: to appear [bibtex] [pdf]
[1]	Fixed-Parameter Tractability of Dependency QBF with Structural Parameters Robert Ganian, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider Principles of Knowledge Representation and Reasoning: Proceedings of the Seventeenth International Conference, KR 2020, 2020. Note: to appear [bibtex]