Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

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.
  • Anna Rapberger
  • 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

50 results
2023
[50]Circuit Minimization with QBF-Based Exact Synthesis
Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, 2023, AAAI Press.
Note: to appear
[bibtex]
[49]Inconsistent Cores for ASP: The Perks and Perils of Non-Monotonicity
Johannes K. Fichte, Markus Hecher, Stefan Szeider
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, 2023, AAAI Press.
Note: to appear
[bibtex]
2022
[48]SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
(Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:18, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[47]Learning Large Bayesian Networks with Expert Constraints
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
38th Conference on Uncertainty in Artificial Intelligence (UAI 2022), Eindhoven, Netherlands, August 1–5, 2022 (James Cussens, Kun Zhang, eds.), pages 180:1592–1601, 2022.
[bibtex] [pdf]
[46]A SAT Approach to Twin-Width
André Schidler, Stefan Szeider
Proceedings of ALENEX 2022, the 24nd SIAM Symposium on Algorithm Engineering and Experiments (Cynthia A. Phillips, Bettina Speckmann, eds.), pages 67–77, 2022, Society for Industrial and Applied Mathematics (SIAM).
[bibtex] [pdf] [doi]
[45]A SAT Attack on Rota’s Basis Conjecture
Markus Kirchweger, Manferd Scheucher, Stefan Szeider
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel (Kuldeep S. Meel, Ofer Strichman, eds.), volume 236 of LIPIcs, pages 4:1–4:18, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[44]Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, Andre Schidler, Kirill Simonov, Stefan Szeider
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel (Kuldeep S. Meel, Ofer Strichman, eds.), volume 236 of LIPIcs, pages 15:1–15:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[43]Finding a Cluster in Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
30th Annual European Symposium on Algorithms (ESA 2022) (Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:14, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[42]Tractable Abstract Argumentation via Backdoor-Treewidth
Wolfgang Dvorak, Markus Hecher, Matthias König, Andre Schidler, Stefan Szeider, Stefan Woltran
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 5608–5615, 2022, AAAI Press.
[bibtex] [pdf]
[41]Equivalence in Argumentation Frameworks with a Claim-centric View – Classical Results with Novel Ingredients
Ringo Baumann, Anna Rapberger, Markus Ulbricht
Proceedings of AAAI-22, the Thirty-Sixth AAAI Conference on Artificial Intelligence, pages , 2022, The AAAI Press.
Note: To appear
[bibtex]
2021
[40]Finding the Hardest Formulas for Resolution
Tomáš Peitl, Stefan Szeider
Journal of Artificial Intelligence Research, volume 72, pages 69–97, 2021.
Note: Conference Award Track, best paper CP 2020
[bibtex] [doi]
[39]New Width Parameters for SAT and Sharp-SAT
Robert Ganian, Stefan Szeider
Artificial Intelligence, volume 295, pages 103460, 2021.
[bibtex] [pdf] [doi]
[38]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]
[37]Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs
Viktor Besin, Markus Hecher, Stefan Woltran
Theory Pract. Log. Program., volume 21, number 5, pages 575–592, 2021.
[bibtex] [pdf] [doi]
[36]Learning fast-inference Bayesian networks
Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Proceedings of NeurIPS 2021, the Thirty-fifth Conference on Neural Information Processing Systems (M. Ranzato, A. Beygelzimer, K. Nguyen, P.S. Liang, J.W. Vaughan, Y. Dauphin, eds.), pages 17852–17863, 2021.
[bibtex] [pdf]
[35]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]
[34]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]
[33]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]
[32]Finding the Hardest Formulas for Resolution (Extended Abstract)
Tomáš 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]
[31]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]
[30]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]
[29]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]
[28]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]
[27]Parallel Model Counting with CUDA: Algorithm Engineering for Efficient Hardware Utilization
Johannes Klaus Fichte, Markus Hecher, Valentin Roland
27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021 (Laurent D. Michel, ed.), volume 210 of LIPIcs, pages 24:1–24:20, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[26]Complications for Computational Experiments from Modern Processors
Johannes Klaus Fichte, Markus Hecher, Ciaran McCreesh, Anas Shahab
27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021 (Laurent D. Michel, ed.), volume 210 of LIPIcs, pages 25:1–25:21, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[25]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]
[24]Decomposition-Guided Reductions for Argumentation and Treewidth
Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood, Arne Meier
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021 (Zhi-Hua Zhou, ed.), pages 1880–1886, 2021, ijcai.org.
[bibtex] [pdf] [doi]
[23]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]
[22]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]
[21]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]
[20]Graph-Classes of Argumentation Frameworks with Collective Attacks
Wolfgang Dvorák, Matthias König, Stefan Woltran
Proceedings of the 17th European Conference on Logics in Artificial Intelligence (JELIA) (Wolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak, eds.), volume 12678 of Lecture Notes in Computer Science, pages 3–17, 2021, Springer Verlag.
[bibtex] [pdf]
[19]A Reduct-Driven Study of Argumentation Frameworks With Collective Attacks
Wolfgang Dvo\vrák, Matthias König, Markus Ulbricht, Stefan Woltran
Proceedings of the 19th International Workshop on Non-Monotonic Reasoning (NMR) 2021, co-located with the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-5, 2021, 2021.
[bibtex] [pdf]
[18]On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length
Wolfgang Dvorák, Matthias König, Stefan Woltran
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021 (Meghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem, eds.), pages 671–675, 2021.
[bibtex] [pdf] [doi]
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 Trans. Comput. Theory, volume 12, number 4, pages 22:1–22:32, 2020.
[bibtex] [pdf] [doi]
[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] [doi]
[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áš 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]

 

News

  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »
  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.