TU Wien Informatics

Stefan Szeider

Univ.Prof. Mag.rer.nat. Dr.rer.nat.

Research Focus

Research Areas

  • Combinatorial Optimization, Automated Reasoning, Algorithms, satisfiability, computational complexity, Fixed Parameter Tractability, Constraint satisfaction, Artificial Intelligence, Networks
Stefan Szeider

About

Design and analysis of efficient algorithms for the solution of hard problems that arise in logic, artificial intelligence, and networks. Theory and Application of SAT (satisfiability) and constraint satisfaction methods. Establishment of theoretical limits for algorithmic techniques.

Roles

Note: Due to the rollout of TU Wien’s new publication database, the list below may be slightly outdated. Once the migration is complete, everything will be up to date again.

2022

2021

  • New width parameters for SAT and #SAT / Ganian, R., & Szeider, S. (2021). New width parameters for SAT and #SAT. Artificial Intelligence, 295(103460), 103460. https://doi.org/10.1016/j.artint.2021.103460
  • Finding the Hardest Formulas for Resolution (Extended Abstract) / Peitl, T., & Szeider, S. (2021). Finding the Hardest Formulas for Resolution (Extended Abstract). In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada, International. https://doi.org/10.24963/ijcai.2021/657
  • Computing Optimal Hypertree Decompositions with SAT / Schidler, A., & Szeider, S. (2021). Computing Optimal Hypertree Decompositions with SAT. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada, International. https://doi.org/10.24963/ijcai.2021/196
  • SAT Modulo Symmetries for Graph Generation / Kirchweger, M., & Szeider, S. (2021). SAT Modulo Symmetries for Graph Generation. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) (pp. 1–16). LIPICS. https://doi.org/10.4230/LIPIcs.CP.2021.34
  • Certified DQBF Solving by Definition Extraction / Reichl, F.-X., Slivovsky, F., & Szeider, S. (2021). Certified DQBF Solving by Definition Extraction. In Theory and Applications of Satisfiability Testing – SAT 2021 (pp. 499–517). LNCS / Springer. https://doi.org/10.1007/978-3-030-80223-3_34
  • SAT-based Decision Tree Learning for Large Data Sets / Schidler, A., & Szeider, S. (2021). SAT-based Decision Tree Learning for Large Data Sets. In Thirty-Fifth AAAI Conference on Artificial Intelligence (pp. 3904–3912). AAAI Press. http://hdl.handle.net/20.500.12708/58603
  • Parameterized Complexity of Small Decision Tree Learning / Ordyniak, S., & Szeider, S. (2021). Parameterized Complexity of Small Decision Tree Learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence (pp. 1–9). AAAI Press. http://hdl.handle.net/20.500.12708/58602
  • Turbocharging Treewidth-Bounded Bayesian Network Structure Learning / Ramaswamy, V. P., & Szeider, S. (2021). Turbocharging Treewidth-Bounded Bayesian Network Structure Learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence (pp. 3895–3903). AAAI Press. http://hdl.handle.net/20.500.12708/58598
  • The Parameterized Complexity of Clustering Incomplete Data / Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2021). The Parameterized Complexity of Clustering Incomplete Data. In Thirty-Fifth AAAI Conference on Artificial Intelligence (pp. 7296–7304). AAAI Press. http://hdl.handle.net/20.500.12708/58587
  • Threshold Treewidth and Hypertree Width / Ganian, R., Schidler, A., Sorge, M., & Szeider, S. (2021). Threshold Treewidth and Hypertree Width. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI - International Joint Conference on Artificial Intelligence, Stockholm, EU. https://doi.org/10.24963/ijcai.2020/263
  • Chapter 17. Fixed-Parameter Tractability / Samer, M., & Szeider, S. (2021). Chapter 17. Fixed-Parameter Tractability. In A. Biere, M. Heule, H. van Maaren, & T. Walsh (Eds.), Frontiers in Artificial Intelligence and Applications. IOS Press. https://doi.org/10.3233/faia201000

2020

  • On Existential MSO and Its Relation to ETH / Ganian, R., Haan, R. de, Kanj, I., & Szeider, S. (2020). On Existential MSO and Its Relation to ETH. ACM Transactions on Computation Theory, 12(4), 1–32. https://doi.org/10.1145/3417759
  • Fixed-Parameter Tractability of Dependency QBF with Structural Parameters / Ganian, R., Peitl, T., Slivovsky, F., & Szeider, S. (2020). Fixed-Parameter Tractability of Dependency QBF with Structural Parameters. In Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning. 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, Non-EU. https://doi.org/10.24963/kr.2020/40
  • Short Q-Resolution Proofs with Homomorphisms / Shukla, A., Slivovsky, F., & Szeider, S. (2020). Short Q-Resolution Proofs with Homomorphisms. In Theory and Applications of Satisfiability Testing – SAT 2020 (pp. 412–428). LNCS. https://doi.org/10.1007/978-3-030-51825-7_29
  • Breaking Symmetries with RootClique and LexTopSort / Fichte, J. K., Hecher, M., & Szeider, S. (2020). Breaking Symmetries with RootClique and LexTopSort. In Lecture Notes in Computer Science (pp. 286–303). https://doi.org/10.1007/978-3-030-58475-7_17 / Projects: HYPAR, START
  • A Time Leap Challenge for SAT-Solving / Fichte, J. K., Hecher, M., & Szeider, S. (2020). A Time Leap Challenge for SAT-Solving. In Lecture Notes in Computer Science (pp. 267–285). https://doi.org/10.1007/978-3-030-58475-7_16 / Projects: HYPAR, START
  • MaxSAT-Based Postprocessing for Treedepth / Peruvemba Ramaswamy, V., & Szeider, S. (2020). MaxSAT-Based Postprocessing for Treedepth. In Lecture Notes in Computer Science (pp. 478–495). LNCS. https://doi.org/10.1007/978-3-030-58475-7_28
  • Finding the Hardest Formulas for Resolution / Peitl, T., & Szeider, S. (2020). Finding the Hardest Formulas for Resolution. In Lecture Notes in Computer Science (pp. 514–530). LNCS. https://doi.org/10.1007/978-3-030-58475-7_30
  • Formalizing Graph Trail Properties in Isabelle/HOL / Kovács, L., Lachnitt, H., & Szeider, S. (2020). Formalizing Graph Trail Properties in Isabelle/HOL. In Lecture Notes in Computer Science (pp. 190–205). LNCS. https://doi.org/10.1007/978-3-030-53518-6_12
  • A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth / Slivovsky, F., & Szeider, S. (2020). A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth. In Theory and Applications of Satisfiability Testing – SAT 2020 (pp. 267–276). LNCS. https://doi.org/10.1007/978-3-030-51825-7_19
  • On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank / Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2020). On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank. In Proceedings of the AAAI Conference on Artificial Intelligence (pp. 3906–3913). AAAI Press. https://doi.org/10.1609/aaai.v34i04.5804
  • Computing Optimal Hypertree Decompositions / Schidler, A., & Szeider, S. (2020). Computing Optimal Hypertree Decompositions. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 1–11). siam. https://doi.org/10.1137/1.9781611976007.1

2019

  • A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy / Haan, R. de, & Szeider, S. (2019). A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. Algorithms, 12(9), 188. https://doi.org/10.3390/a12090188
  • A SAT Approach to Branchwidth / Lodha, N., Ordyniak, S., & Szeider, S. (2019). A SAT Approach to Branchwidth. ACM Transactions on Computational Logic, 20(3), 1–24. https://doi.org/10.1145/3326159
  • Dependency Learning for QBF / Peitl, T., Slivovsky, F., & Szeider, S. (2019). Dependency Learning for QBF. Journal of Artificial Intelligence Research, 65, 181–208. https://doi.org/10.1613/jair.1.11529
  • On the parameterized complexity of (k, s)-SAT / Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k, s)-SAT. Information Processing Letters, 143, 34–36. https://doi.org/10.1016/j.ipl.2018.11.005
  • Parameterized Complexity Results for the Completion and Clustering of Incomplete Data / Szeider, S., Ganian, R., Kanj, I., & Ordyniak, S. (2019). Parameterized Complexity Results for the Completion and Clustering of Incomplete Data. Kocoon Workshop, Arras, Frankreich, EU. http://hdl.handle.net/20.500.12708/86961
  • Computational Thinking und ADA.wien / Szeider, S. (2019). Computational Thinking und ADA.wien. eEducation Fachtagung, Wien, Austria. http://hdl.handle.net/20.500.12708/86955
  • Proof Complexity of Fragments of Long-Distance Q-Resolution / Peitl, T., Slivovsky, F., & Szeider, S. (2019). Proof Complexity of Fragments of Long-Distance Q-Resolution. In Lecture Notes in Computer Science. Theory and Application of Satisfiability Testing -- SAT, Guangzhou, Non-EU. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-030-24258-9
  • Combining Resolution-Path Dependencies with Dependency Learning / Peitl, T., Slivovsky, F., & Szeider, S. (2019). Combining Resolution-Path Dependencies with Dependency Learning. In Lecture Notes in Computer Science. Int. Conference on Theory and Applications of Satisfiability Testing, Trento, EU. LNCS. https://doi.org/10.1007/978-3-030-24258-9
  • SAT-Encodings for Treecut Width and Treedepth / Ganian, R., Lodha, N., Ordyniak, S., & Szeider, S. (2019). SAT-Encodings for Treecut Width and Treedepth. In S. G. Kobourov & H. Meyerhenke (Eds.), Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM. https://doi.org/10.1137/1.9781611975499

2018

  • An SMT Approach to Fractional Hypertree Width / Fichte, J., Hecher, M., Lodha, N., & Szeider, S. (2018). An SMT Approach to Fractional Hypertree Width. In J. Hooker (Ed.), Principles and Practice of Constraint Programming, 24th International Conference, CP 2018 (pp. 109–127). Springer-Verlag. https://doi.org/10.1007/978-3-319-98334-9_8 / Project: START
  • Long-Distance Q-Resolution with Dependency Schemes / Peitl, T., Slivovsky, F., & Szeider, S. (2018). Long-Distance Q-Resolution with Dependency Schemes. Journal of Automated Reasoning, 63(1), 127–155. https://doi.org/10.1007/s10817-018-9467-3
  • Meta-kernelization using well-structured modulators / Eiben, E., Ganian, R., & Szeider, S. (2018). Meta-kernelization using well-structured modulators. Discrete Applied Mathematics, 248, 153–167. https://doi.org/10.1016/j.dam.2017.09.018
  • Polynomial-Time Validation of QCDCL Certificates / Peitl, T., Slivovsky, F., & Szeider, S. (2018). Polynomial-Time Validation of QCDCL Certificates. In O. Beyersdorff & C. M. Wintersteiger (Eds.), Theory and Applications of Satisfiability Testing – SAT 2018 (pp. 253–269). Springer-Verlag, Lecture Notes in Artificial Intelligence 8268. https://doi.org/10.1007/978-3-319-94144-8_16
  • Portfolio-Based Algorithm Selection for Circuit QBFs / Hoos, H. H., Peitl, T., Slivovsky, F., & Szeider, S. (2018). Portfolio-Based Algorithm Selection for Circuit QBFs. In Lecture Notes in Computer Science (pp. 195–209). Springer-Verlag. https://doi.org/10.1007/978-3-319-98334-9_13
  • Parameterized Algorithms for the Matrix Completion Problem / Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2018). Parameterized Algorithms for the Matrix Completion Problem. In Proceeding of ICML (pp. 1642–1651). Journal of Machine Learning Research. http://hdl.handle.net/20.500.12708/57440

2017

  • The Treewidth of Proofs / Müller, M., & Szeider, S. (2017). The Treewidth of Proofs. Information and Computation, 255, 147–164. http://hdl.handle.net/20.500.12708/147673
  • Backdoors into heterogeneous classes of SAT and CSP / Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., & Živný, S. (2017). Backdoors into heterogeneous classes of SAT and CSP. Journal of Computer and System Sciences, 85, 38–56. https://doi.org/10.1016/j.jcss.2016.10.007
  • Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting / Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. ACM Transactions on Algorithms, 13(2), 1–32. https://doi.org/10.1145/3014587
  • On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances / Haan, R. D., Kanj, I., & Szeider, S. (2017). On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances. ACM Transactions on Computational Logic, 18(3), 1–46. https://doi.org/10.1145/3091528
  • Parameterized complexity classes beyond para-NP / de Haan, R., & Szeider, S. (2017). Parameterized complexity classes beyond para-NP. Journal of Computer and System Sciences, 87, 16–57. https://doi.org/10.1016/j.jcss.2017.02.002
  • Solving Problems on Graphs of High Rank-Width / Eiben, E., Ganian, R., & Szeider, S. (2017). Solving Problems on Graphs of High Rank-Width. Algorithmica, 80(2), 742–771. https://doi.org/10.1007/s00453-017-0290-8
  • Dependency Learning for QBF / Peitl, T., Slivovsky, F., & Szeider, S. (2017). Dependency Learning for QBF. In Theory and Applications of Satisfiability Testing – SAT 2017 ; Gaspers, Serge; Walsh, Toby. Cham. https://doi.org/10.1007/978-3-319-66263-3_19
  • Backdoors for Constraint Satisfaction / Szeider, S. (2017). Backdoors for Constraint Satisfaction. Workshop Gutin 60, Großbritanien, EU. http://hdl.handle.net/20.500.12708/86682
  • Capturing Structure in Instances of the Propositional Satisfiability Problem / Szeider, S. (2017). Capturing Structure in Instances of the Propositional Satisfiability Problem. ÖMG-DMV-Congress 2017, Salzburg, Austria. http://hdl.handle.net/20.500.12708/86681
  • Get Satisfaction: Das Erfüllbarkeitsproblem in Theorie und Praxis / Szeider, S. (2017). Get Satisfaction: Das Erfüllbarkeitsproblem in Theorie und Praxis. 9. Informatiktag 2017, Tu Wien, Austria. http://hdl.handle.net/20.500.12708/86680
  • A SAT Approach to Branchwidth / Lodha, N., Ordyniak, S., & Szeider, S. (2017). A SAT Approach to Branchwidth. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017) (pp. 4894–4898). http://hdl.handle.net/20.500.12708/57272
  • Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable / Ramanujan, M. S., & Szeider, S. (2017). Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable. In Thirty-First AAAI Conference on Artificial Intelligence (pp. 3929–3935). http://hdl.handle.net/20.500.12708/57271
  • New Width Parameters for Model Counting / Ganian, R., & Szeider, S. (2017). New Width Parameters for Model Counting. In Theory and Applications of Satisfiability Testing – SAT 2017 (pp. 38–52). International Conference on Theory and Applications of Satisfiability Testing. https://doi.org/10.1007/978-3-319-66263-3_3
  • SAT-Encodings for Special Treewidth and Pathwidth / Lodha, N., Ordyniak, S., & Szeider, S. (2017). SAT-Encodings for Special Treewidth and Pathwidth. In Theory and Applications of Satisfiability Testing – SAT 2017 (pp. 429–445). Springer International Publishing AG 2017. https://doi.org/10.1007/978-3-319-66263-3_27
  • Backdoor Treewidth for SAT / Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Backdoor Treewidth for SAT. In Theory and Applications of Satisfiability Testing – SAT 2017 (pp. 20–37). Springer-Verlag. https://doi.org/10.1007/978-3-319-66263-3_2
  • Combining Treewidth and Backdoors for CSP / Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Combining Treewidth and Backdoors for CSP. In 34th Symposium on Theoretical Aspects of Computer Science (pp. 429–445). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.STACS.2017.36
  • The Constraint Satisfaction Problem: Complexity and Approximability / Szeider, S., Ordyniak, S., & Gaspers, S. (2017). The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability (pp. 137–157). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. http://hdl.handle.net/20.500.12708/29616

2016

  • Meta-kernelization with structural parameters / Ganian, R., Slivovsky, F., & Szeider, S. (2016). Meta-kernelization with structural parameters. Journal of Computer and System Sciences, 82(2), 333–346. https://doi.org/10.1016/j.jcss.2015.08.003
  • Backdoors to q-Horn / Gaspers, S., Ordyniak, S., Ramanujan, M. S., Saurabh, S., & Szeider, S. (2016). Backdoors to q-Horn. Algorithmica, 74(1), 540–557. https://doi.org/10.1007/s00453-014-9958-5
  • Soundness of Q-resolution with dependency schemes / Slivovsky, F., & Szeider, S. (2016). Soundness of Q-resolution with dependency schemes. Theoretical Computer Science, 612, 83–101. https://doi.org/10.1016/j.tcs.2015.10.020
  • Quantified conjunctive queries on partially ordered sets / Bova, S., Ganian, R., & Szeider, S. (2016). Quantified conjunctive queries on partially ordered sets. Theoretical Computer Science, 618, 72–84. https://doi.org/10.1016/j.tcs.2016.01.010
  • Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting / Ganian, R., Ramanujan, M. S., & Szeider, S. (2016). Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. In R. Krauthgamer (Ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1670–1681). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974331.ch114
  • Long Distance Q-Resolution with Dependency Schemes / Peitl, T., Slivovsky, F., & Szeider, S. (2016). Long Distance Q-Resolution with Dependency Schemes. In Lecture Notes in Computer Science ; Creignou, Nadia; Le Berre, Daniel. Cham. https://doi.org/10.1007/978-3-319-40970-2_31
  • Capturing Structure in SAT and Related Problems / Szeider, S. (2016). Capturing Structure in SAT and Related Problems. Theoretical Foundations of SAT Solving Workshop, Toronto, Kanada, Non-EU. http://hdl.handle.net/20.500.12708/86384
  • Capturing Structure in SAT and Related Problems / Szeider, S. (2016). Capturing Structure in SAT and Related Problems. International Workshop on Graph Structure and Satisfiability Testing, Bordeaux, France, EU. http://hdl.handle.net/20.500.12708/86383
  • Polynomial-Time Construction of Optimal MPI Derived Datatype Trees / Ganian, R., Kalany, M., Szeider, S., & Träff, J. L. (2016). Polynomial-Time Construction of Optimal MPI Derived Datatype Trees. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE 30th International Parallel and Distributed Processing Symposium (IPDPS 2016), Chicago, Illinois, USA, Non-EU. IEEE Computer Society. https://doi.org/10.1109/ipdps.2016.13 / Project: EPiGRAM
  • Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics / de Haan, R., & Szeider, S. (2016). Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning - KR 2016 (pp. 453–462). http://hdl.handle.net/20.500.12708/56825
  • A SAT Approach to Branchwidth / Lodha, N., Ordyniak, S., & Szeider, S. (2016). A SAT Approach to Branchwidth. In Proceedings of SAT 2016: Theory and Applications of Satisfiability Testing - SAT 2016 (pp. 179–195). http://hdl.handle.net/20.500.12708/56670
  • On Existential MSO and its Relation to ETH / Ganian, R., de Haan, R., Kanj, I., & Szeider, S. (2016). On Existential MSO and its Relation to ETH. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (pp. 1–14). http://hdl.handle.net/20.500.12708/56669
  • Backdoors to Tractable Valued CSP / Ganian, R., Ramanujan, M. S., & Szeider, S. (2016). Backdoors to Tractable Valued CSP. In Principles and Practice of Constraint Programming (Proceedings of 22nd CP) (pp. 233–250). LNCS. http://hdl.handle.net/20.500.12708/56665
  • Backdoor Trees for Answer Set Programming / Fichte, J., & Szeider, S. (2016). Backdoor Trees for Answer Set Programming (DBAI-TR-2016-98). http://hdl.handle.net/20.500.12708/39079 / Project: START

2015

  • Parameterized and subexponential-time complexity ofsatisfiability problems and applications / Kanj, I., & Szeider, S. (2015). Parameterized and subexponential-time complexity ofsatisfiability problems and applications. Theoretical Computer Science, 607, 282–295. https://doi.org/10.1016/j.tcs.2015.08.029
  • Model Checking Existential Logic on Partially Ordered Sets / Bova, S., Ganian, R., & Szeider, S. (2015). Model Checking Existential Logic on Partially Ordered Sets. ACM Transactions on Computational Logic, 17(2), 1–35. https://doi.org/10.1145/2814937
  • Model Counting for CNF Formulas of Bounded Modular Treewidth / Paulusma, D., Slivovsky, F., & Szeider, S. (2015). Model Counting for CNF Formulas of Bounded Modular Treewidth. Algorithmica, 76(1), 168–194. https://doi.org/10.1007/s00453-015-0030-x
  • Quantifier Reordering for QBF / Slivovsky, F., & Szeider, S. (2015). Quantifier Reordering for QBF. Journal of Automated Reasoning, 56(4), 459–477. https://doi.org/10.1007/s10817-015-9353-1
  • A SAT Approach to Clique-Width / Heule, M. J. H., & Szeider, S. (2015). A SAT Approach to Clique-Width. ACM Transactions on Computational Logic, 16(3), 1–27. https://doi.org/10.1145/2736696
  • On finding optimal polytrees / Gaspers, S., Koivisto, M., Liedloff, M., Ordyniak, S., & Szeider, S. (2015). On finding optimal polytrees. Theoretical Computer Science, 592, 49–58. https://doi.org/10.1016/j.tcs.2015.05.012
  • A Complete Parameterized Complexity Analysis of Bounded Planning / Jonsson, P., Ordyniak, S., & Szeider, S. (2015). A Complete Parameterized Complexity Analysis of Bounded Planning. Journal of Computer and System Sciences, 81(7), 1311–1332. https://doi.org/10.1016/j.jcss.2015.04.002
  • On the Subexponential-Time Complexity of CSP / De Haan, R., Kanj, I., & Szeider, S. (2015). On the Subexponential-Time Complexity of CSP. Journal of Artificial Intelligence Research, 52, 203–234. https://doi.org/10.1613/jair.4540
  • Backdoors to Normality for Disjunctive Logic Programs / Fichte, J. K., & Szeider, S. (2015). Backdoors to Normality for Disjunctive Logic Programs. ACM Transactions on Computational Logic, 17(1), 1–23. https://doi.org/10.1145/2818646 / Project: START
  • Backdoors to tractable answer-set programming / Fichte, J. K., & Szeider, S. (2015). Backdoors to tractable answer-set programming. Artificial Intelligence, 220, 64–103. https://doi.org/10.1016/j.artint.2014.12.001 / Project: START
  • A Survey on Parameterized Complexity and SAT / Szeider, S. (2015). A Survey on Parameterized Complexity and SAT. Dagstuhl Seminar, Dagstuhl, Deutschland, EU. http://hdl.handle.net/20.500.12708/86232
  • Solving Problems on Graphs of High Rank-Width / Eiben, E., Ganian, R., & Szeider, S. (2015). Solving Problems on Graphs of High Rank-Width. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (pp. 314–326). LNCS. http://hdl.handle.net/20.500.12708/56453
  • Community Structure Inspired Algorithms for SAT and #SAT / Ganian, R., & Szeider, S. (2015). Community Structure Inspired Algorithms for SAT and #SAT. In Proceedings of the 18th International Conference on Theory and Applications of Satisfiability Testing (pp. 223–238). LNCS / Springer. http://hdl.handle.net/20.500.12708/56452
  • Algorithmic Applications of Tree-Cut Width / Ganian, R., Kim, E. J., & Szeider, S. (2015). Algorithmic Applications of Tree-Cut Width. In Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science 2015 (pp. 348–361). http://hdl.handle.net/20.500.12708/56451
  • Meta-kernelization using Well-structured Modulators / Eiben, E., Ganian, R., & Szeider, S. (2015). Meta-kernelization using Well-structured Modulators. In T. Husfeldt & I. Kanj (Eds.), 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (pp. 114–126). LIPICs. https://doi.org/10.4230/LIPIcs.IPEC.2015.114
  • Parameterized Complexity Results for Agenda Safety in Judgment Aggregation / de Haan, R., Endriss, U., & Szeider, S. (2015). Parameterized Complexity Results for Agenda Safety in Judgment Aggregation. In G. Weiss, P. Yolum, R. H. Bordini, & E. Elkind (Eds.), Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems - AAMAS 2015 (pp. 127–136). http://hdl.handle.net/20.500.12708/56187
  • Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP / de Haan, R., & Szeider, S. (2015). Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP. In G. F. Italiano, T. Margaria, J. Pokorný, J.-J. Quisquater, & R. Wattenhofer (Eds.), Lecture Notes in Computer Science. LNCS. https://doi.org/10.1007/978-3-662-46078-8

2014

2013

  • Parameterized Complexity Results for Exact Bayesian Network Structure Learning / Ordyniak, S., & Szeider, S. (2013). Parameterized Complexity Results for Exact Bayesian Network Structure Learning. Journal of Artificial Intelligence Research, 46, 263–302. https://doi.org/10.1613/jair.3744 / Project: Complex Reason
  • Satisfiability of acyclic and almost acyclic CNF formulas / Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85–99. https://doi.org/10.1016/j.tcs.2012.12.039 / Project: Complex Reason
  • The Parameterized Complexity of Constraint Satisfaction and Reasoning / Szeider, S. (2013). The Parameterized Complexity of Constraint Satisfaction and Reasoning. In H. Tompits, S. Abreu, J. Oetsch, J. Pührer, D. Seipel, M. Umeda, & A. Wolf (Eds.), Applications of Declarative Programming and Knowledge Management (pp. 27–37). Springer / LNCS. https://doi.org/10.1007/978-3-642-41524-1_2 / Project: Complex Reason
  • Revisiting Space in Proof Complexity: Treewidth and Pathwidth / Müller, M., & Szeider, S. (2013). Revisiting Space in Proof Complexity: Treewidth and Pathwidth. In K. Chatterjee & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 704–716). Springer / LNCS. https://doi.org/10.1007/978-3-642-40313-2_62 / Project: Complex Reason
  • SAT Approach to Clique-Width / Szeider, S. (2013). SAT Approach to Clique-Width. Workshop on Graph Classes, Optimization, and Width Parameters (GROW), Santorini Island, Greece, EU. http://hdl.handle.net/20.500.12708/85669 / Project: Complex Reason
  • Parameterized Complexity / Szeider, S. (2013). Parameterized Complexity. the International SAT/SMT Summer School, Espoo, Finland, EU. http://hdl.handle.net/20.500.12708/85668 / Project: Complex Reason
  • Model Counting for Formulas of Bounded Clique-Width / Slivovsky, F., & Szeider, S. (2013). Model Counting for Formulas of Bounded Clique-Width. In L. Cai, S.-W. Cheng, & T.-W. Lam (Eds.), Algorithms and Computation (pp. 677–687). Springer / LNCS. https://doi.org/10.1007/978-3-642-45030-3_63 / Project: Complex Reason
  • Backdoors to q-Horn / Gaspers, S., Ordyniak, S., Ramanujan, M. S., Saurabh, S., & Szeider, S. (2013). Backdoors to q-Horn. In N. Portier & T. Wilke (Eds.), 30th Symposium on Theoretical Aspects of Computer Science (STACS´13) (pp. 67–79). Dagstuhl Publishing. http://hdl.handle.net/20.500.12708/54875 / Project: Complex Reason
  • Model Counting for CNF Formulas of Bounded Modular Treewidth / Paulusma, D., Slivovsky, F., & Szeider, S. (2013). Model Counting for CNF Formulas of Bounded Modular Treewidth. In N. Portier & T. Wilke (Eds.), 30th Symposium on Theoretical Aspects of Computer Science (STACS´13) (pp. 55–66). Dagstuhl Publishing. http://hdl.handle.net/20.500.12708/54874 / Project: Complex Reason
  • Parameterized Complexity and Kernel Bounds for Hard Planning Problems / Bäckström, C., Jonsson, P., Ordyniak, S., & Szeider, S. (2013). Parameterized Complexity and Kernel Bounds for Hard Planning Problems. In P. G. Spirakis & M. Serna (Eds.), Lecture Notes in Computer Science. Springer / LNCS. https://doi.org/10.1007/978-3-642-38233-8 / Project: Complex Reason
  • Upper and Lower Bounds for Weak Backdoor Set Detection / Misra, N., Ordyniak, S., Raman, V., & Szeider, S. (2013). Upper and Lower Bounds for Weak Backdoor Set Detection. In M. Järvisalo & A. Van Gelder (Eds.), Lecture Notes in Computer Science. Springer / LNCS. https://doi.org/10.1007/978-3-642-39071-5 / Project: Complex Reason
  • A SAT Approach to Clique-Width / Heule, M., & Szeider, S. (2013). A SAT Approach to Clique-Width. In M. Järvisalo & A. Van Gelder (Eds.), Lecture Notes in Computer Science. Springer / LNCS. https://doi.org/10.1007/978-3-642-39071-5 / Project: Complex Reason
  • Local Backbones / de Haan, R., Kanj, I., & Szeider, S. (2013). Local Backbones. In M. Järvisalo & A. Van Gelder (Eds.), Lecture Notes in Computer Science. LNCS / Springer. https://doi.org/10.1007/978-3-642-39071-5 / Project: Complex Reason
  • On the Subexponential Time Complexity of CSP / Kanj, I., & Szeider, S. (2013). On the Subexponential Time Complexity of CSP. In M. desJardins & M. Littman (Eds.), Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI´13) (pp. 459–465). AAAI Press. http://hdl.handle.net/20.500.12708/54867 / Project: Complex Reason
  • Meta-kernelization with Structural Parameters / Ganian, R., Slivovsky, F., & Szeider, S. (2013). Meta-kernelization with Structural Parameters. In K. Chatterjee & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 457–468). Springer / LNCS. https://doi.org/10.1007/978-3-642-40313-2_41 / Project: Complex Reason
  • Backdoors to Normality for Disjunctive Logic Programs / Fichte, J., & Szeider, S. (2013). Backdoors to Normality for Disjunctive Logic Programs. In M. desJardins & M. Littman (Eds.), Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI´13) (pp. 320–327). AAAI Press. http://hdl.handle.net/20.500.12708/54865 / Project: Complex Reason
  • Strong Backdoors to Bounded Treewidth SAT / Gaspers, S., & Szeider, S. (2013). Strong Backdoors to Bounded Treewidth SAT. In O. Reingold (Ed.), 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. https://doi.org/10.1109/focs.2013.59 / Project: Complex Reason
  • Parameterized Complexity Results for Plan Reuse / de Haan, R., Roubickova, A., & Szeider, S. (2013). Parameterized Complexity Results for Plan Reuse. In M. desJardins & M. Littman (Eds.), Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI´13) (pp. 224–231). AAAI Press. http://hdl.handle.net/20.500.12708/54863 / Project: Complex Reason
  • Backdoors to Abduction / Pfandler, A., Rümmele, S., & Szeider, S. (2013). Backdoors to Abduction. In F. Rossi (Ed.), Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (pp. 1046–1052). AAAI Press. http://hdl.handle.net/20.500.12708/54790 / Projects: Complex Reason, FAIR
  • Variable Dependencies and Q-Resolution / Slivovsky, F., & Szeider, S. (2013). Variable Dependencies and Q-Resolution. In F. Lonsing & M. Seidl (Eds.), International Workshop on Quantified Boolean Formulas 2013 Informal Workshop Report (pp. 22–29). http://hdl.handle.net/20.500.12708/54888 / Project: Complex Reason
  • Capturing Structure in Hard Combinatorial Problems. / Szeider, S. (2013). Capturing Structure in Hard Combinatorial Problems. In Proceedings of the International Conference on Tools with Artificial Intelligence (ICTAI). The IEEE International Conference on Tools with Artificial Intelligence, Special Track on SAT and CSP Technologies (ICTAI), Washington D.C., USA, Non-EU. http://hdl.handle.net/20.500.12708/54879 / Project: Complex Reason
  • Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem / Bliem, B., Pichler, R., & Woltran, S. (2013). Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem. In G. Gutin & S. Szeider (Eds.), Parameterized and Exact Computation (pp. 28–40). Springer. https://doi.org/10.1007/978-3-319-03898-8_4 / Project: D-Flat
  • MFCS & CSL 2010 Satellite Workshops: Selected Papers, Fundamenta Informaticae 123 / MFCS & CSL 2010 Satellite Workshops: Selected Papers, Fundamenta Informaticae 123. (2013). In A. Kucera, I. Potapov, A. Ciabattoni, S. Szeider, & R. Freivalds (Eds.), Fundamenta Informaticae. IOS Press. http://hdl.handle.net/20.500.12708/23747 / Project: Complex Reason
  • Parameterized and Exact Computation, 8th International Symposium, IPEC 2013 (LNCS 8246) / Gutin, G., & Szeider, S. (Eds.). (2013). Parameterized and Exact Computation, 8th International Symposium, IPEC 2013 (LNCS 8246). Springer-Verlag. http://hdl.handle.net/20.500.12708/23746 / Project: Complex Reason

2012

  • Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough / Pichler, R., Rümmele, S., Szeider, S., & Woltran, S. (2012). Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. CoRR - Computing Research Repository. http://hdl.handle.net/20.500.12708/163667 / Project: TTPC
  • Editing Graphs to Satisfy Degree Constraints: A Parameterized Approach / Mathieson, L., & Szeider, S. (2012). Editing Graphs to Satisfy Degree Constraints: A Parameterized Approach. Journal of Computer and System Sciences, 78(1), 179–191. https://doi.org/10.1016/j.jcss.2011.02.001
  • On Graph Contractions and Induced Minors / van ’t Hof, P., Kamiński, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2012). On Graph Contractions and Induced Minors. Discrete Applied Mathematics, 160(6), 799–809. https://doi.org/10.1016/j.dam.2010.05.005 / Project: Complex Reason
  • Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming / Gutin, G., Kim, E. J., Soleimanfallah, A., Szeider, S., & Yeo, A. (2012). Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Algorithmica, 64(1), 112–125. https://doi.org/10.1007/s00453-011-9548-8 / Project: Complex Reason
  • Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough / PICHLER, R., RÜMMELE, S., SZEIDER, S., & WOLTRAN, S. (2012). Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. Theory and Practice of Logic Programming, 14(2), 141–164. https://doi.org/10.1017/s1471068412000099 / Project: Complex Reason
  • Augmenting Tractable Fragments of Abstract Argumentation / Dvořák, W., Ordyniak, S., & Szeider, S. (2012). Augmenting Tractable Fragments of Abstract Argumentation. Artificial Intelligence, 186, 157–173. https://doi.org/10.1016/j.artint.2012.03.002 / Projects: Argu, Complex Reason
  • Parameterized Complexity / Szeider, S. (2012). Parameterized Complexity. The Logic and Interactions Winter School, CIRM, Marseille, France, EU. http://hdl.handle.net/20.500.12708/85423 / Project: Complex Reason
  • The Parameterized Complexity of Propositional Satisfiability / Szeider, S. (2012). The Parameterized Complexity of Propositional Satisfiability. Statistical Mechanics of Unsatisfiability and Glasses, Ferry Stockholm-Mariehamn and Hotel Arkipelag, Mariehamn, Åland, EU. http://hdl.handle.net/20.500.12708/85422 / Project: Complex Reason
  • Parameterized Complexity Results for Probabilistic Network Structure Learning / Szeider, S. (2012). Parameterized Complexity Results for Probabilistic Network Structure Learning. Workshop on Applications of Parameterized Algorithms and Complexit, Warwick, UK, EU. http://hdl.handle.net/20.500.12708/85421 / Project: Complex Reason
  • dynPARTIX 2.0 - Dynamic Programming Argumentation Reasoning Tool / Charwat, G., & Dvorak, W. (2012). dynPARTIX 2.0 - Dynamic Programming Argumentation Reasoning Tool. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Proceedings of Computational Models of Argument - Proceedings of COMMA 2012 (pp. 507–508). Frontiers in Artificial Intelligence and Applications / IOS Press. http://hdl.handle.net/20.500.12708/54497 / Project: Argu
  • Comparing the Expressiveness of Argumentation Semantics / Dvorak, W., & Spanring, C. (2012). Comparing the Expressiveness of Argumentation Semantics. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Proceedings of Computational Models of Argument - Proceedings of COMMA 2012 (pp. 261–272). Frontiers in Artificial Intelligence and Applications / IOS Press. http://hdl.handle.net/20.500.12708/54496 / Project: Argu
  • Complexity of logic-based argumentation in Schaefer's framework / Egly, U., Creignou, N., & Schmidt, J. (2012). Complexity of logic-based argumentation in Schaefer’s framework. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Computational Models of Argument (pp. 237–248). IOS Press. http://hdl.handle.net/20.500.12708/54461 / Project: Boolean
  • Backdoors to Normality for Disjunctive Logic Programs / Fichte, J., & Szeider, S. (2012). Backdoors to Normality for Disjunctive Logic Programs. In Y. Lierler & M. Fink (Eds.), Proceedings of the 5th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2012) (pp. 99–113). http://hdl.handle.net/20.500.12708/54323 / Project: Complex Reason
  • Valued-Based Argumentation for Tree-like Value Graphs / Kim, E. J., & Ordyniak, S. (2012). Valued-Based Argumentation for Tree-like Value Graphs. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Fourth International Conference on Computational Models of Argument (Comma 2012) (pp. 378–389). IOS Press. http://hdl.handle.net/20.500.12708/54321 / Projects: Complex Reason, Complexity
  • k-Gap Interval Graphs / Fomin, F. V., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., van Leeuwen, E. J., Vatshelle, M., & Villanger, Y. (2012). k-Gap Interval Graphs. In D. Fernández-Baca (Ed.), LATIN 2012: Theoretical Informatics (pp. 350–361). Lecture Notes in Computer Science / Springer. https://doi.org/10.1007/978-3-642-29344-3_30 / Project: Complex Reason
  • Strong Backdoors to Nested Satisfiability / Gaspers, S., & Szeider, S. (2012). Strong Backdoors to Nested Satisfiability. In A. Cimatti & R. Sebastiani (Eds.), Proceedings of the Fifteen International Conference on Theory and Applications of Satisfiability Testing (SAT 2012) (pp. 58–71). LNCS / Springer. http://hdl.handle.net/20.500.12708/54319 / Project: Complex Reason
  • Computing Resolution-Path Dependencies in Linear Time , / Slivovsky, F., & Szeider, S. (2012). Computing Resolution-Path Dependencies in Linear Time ,. In A. Cimatti & R. Sebastiani (Eds.), Theory and Applications of Satisfiability Testing – SAT 2012 (pp. 58–71). LNCS / Springer. https://doi.org/10.1007/978-3-642-31612-8_6 / Project: Complex Reason
  • Backdoors to Acyclic SAT / Gaspers, S., & Szeider, S. (2012). Backdoors to Acyclic SAT. In Automata, Languages, and Programming (pp. 363–374). Springer-Verlag. https://doi.org/10.1007/978-3-642-31594-7_31 / Project: Complex Reason
  • Don't Be Strict in Local Search! / Gaspers, S., Kim, E. J., Ordyniak, S., Saurabh, S., & Szeider, S. (2012). Don’t Be Strict in Local Search! In J. Hoffmann & B. Selman (Eds.), Proceedings of the 26th Conference on Artificial Intelligence (AAAI 2012) (pp. 486–492). AAAI Press. http://hdl.handle.net/20.500.12708/54316 / Projects: Complex Reason, Complexity
  • On Finding Optimal Polytrees / Gaspers, S., Koivisto, M., Liedloff, M., Ordyniak, S., & Szeider, S. (2012). On Finding Optimal Polytrees. In J. Hoffmann & B. Selman (Eds.), Proceedings of the 26th Conference on Artificial Intelligence (AAAI 2012) (pp. 750–756). AAAI Press. http://hdl.handle.net/20.500.12708/54315 / Project: Complex Reason
  • The Complexity of Planning Revisited - A Parameterized Analysis / Bäckström, C., Chen, Y., Jonsson, P., Ordyniak, S., & Szeider, S. (2012). The Complexity of Planning Revisited - A Parameterized Analysis. In J. Hoffmann & B. Selman (Eds.), Proceedings of the 26th Conference on Artificial Intelligence (AAAI 2012) (pp. 1735–1741). AAAI Press. http://hdl.handle.net/20.500.12708/54314 / Project: Complex Reason
  • Abstract Argumentation via Monadic Second Order Logic / Dvořák, W., Szeider, S., & Woltran, S. (2012). Abstract Argumentation via Monadic Second Order Logic. In E. Hüllermeier, S. Link, T. Fober, & B. Seeger (Eds.), Lecture Notes in Computer Science (pp. 85–98). Lecture Notes in Computer Science / Springer. https://doi.org/10.1007/978-3-642-33362-0_7 / Projects: Argu, Complex Reason
  • Evaluating Abstract Dialectical Frameworks with ASP / Ellmauthaler, S., & Wallner, J. P. (2012). Evaluating Abstract Dialectical Frameworks with ASP. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Proceedings of Computational Models of Argument - Proceedings of COMMA 2012 (pp. 505–506). IOS Press. http://hdl.handle.net/20.500.12708/54186
  • Computational Aspects of cf2 and stage2 Argumentation Semantics. / Dvorak, W., & Gaggl, S. (2012). Computational Aspects of cf2 and stage2 Argumentation Semantics. In B. Verheij, S. Szeider, & S. Woltran (Eds.), Proceedings of Fourth International Conference on Computational Models of Argument (pp. 273–284). “Frontiers in Artificial Intelligence and Applications” series/IOS Press. http://hdl.handle.net/20.500.12708/54177
  • Abstract Argumentation via Monadic Second Order Logic. / Dvorak, W., Szeider, S., & Woltran, S. (2012). Abstract Argumentation via Monadic Second Order Logic. (DBAI-TR-2012-79). http://hdl.handle.net/20.500.12708/37417 / Projects: Argu, Complex Reason
  • Fourth International Conference on Computational Models of Argument (COMMA 2012) / Verheij, B., Szeider, S., & Woltran, S. (Eds.). (2012). Fourth International Conference on Computational Models of Argument (COMMA 2012). IOS Press. http://hdl.handle.net/20.500.12708/23575 / Project: Complex Reason
  • Backdoors to Satisfaction / Gaspers, S., & Szeider, S. (2012). Backdoors to Satisfaction. In H. L. Bodlaender, R. G. Downey, F. Fomin, & D. Marx (Eds.), The Multivariate Algorithmic Revolution and Beyond (pp. 287–317). Springer LNCS. https://doi.org/10.1007/978-3-642-30891-8_15 / Project: Complex Reason
  • The Added Value of Argumentation / Modgil, S., Toni, F., Bex, F., Bratko, I., Chesñevar, C. I., Dvořák, W., Falappa, M. A., Fan, X., Gaggl, S. A., García, A. J., González, M. P., Gordon, T. F., Leite, J., Možina, M., Reed, C., Simari, G. R., Szeider, S., Torroni, P., & Woltran, S. (2012). The Added Value of Argumentation. In S. Ossowski (Ed.), Agreement Technologies (pp. 357–403). Springer Netherlands. https://doi.org/10.1007/978-94-007-5583-3_21

2011

2010

 

Note: Due to the rollout of TU Wien’s new publication database, the list below may be slightly outdated. Once the migration is complete, everything will be up to date again.

  • The Parameterized Complexity of Reasoning Problems
    2010 / ERC Europäischer Forschungsrat

Soon, this page will include additional information such as reference projects, activities as journal reviewer and editor, memberships in councils and committees, and other research activities.

Until then, please visit Stefan Szeider’s research profile in TISS .