Contact

Univ.-Prof. Dr. Stefan Szeider
Institute of Information Systems (184/3)
Vienna University of Technology (TU Wien)
Favoritenstraße 9-11
A-1040 Vienna, Austria

Phone: +43 (1) 58801 18433
Fax: +43 (1) 58801 18493
e-mail: stefan @ szeider.net

Research Interests

My work deals with the computational complexity of problems and their algorithmic solution. In particular I am interested in problems that are intractable in general but may admit efficient solutions for special cases. I have considered various problems arising in computational reasoning, artificial intelligence, and combinatorial optimization. My ambition is to push the intractability frontier for such problems as far as possible, aiming at an efficient solution for instances of practical relevance, and to identify the hard kernel of the general problem. My ultimate goal is to understand the question: What makes a problem hard?

Since 2009 I have been holding an ERC Starting Independent Researcher Grant for the research project "The Parameterized Complexity of Reasoning Problems".

Conference Activities

  • Member of the steering committee of IPEC, the International Symposium on Parameterized and Exact Computation (formerly IWPEC).
  • Member of the steering committe of SAT, the International Conference on Theory and Applications of Satisfiability Testing.
  • Program commitee member of SAT 2012, the Fifteen International Conference on Theory and Applications of Satisfiability Testing June 17-20, 2012, Trento, Italy.
  • Conference co-chair of COMMA 2012, the Fourth International Conference on Computational Models of Argument, September 2012, Vienna, Austria.
  • Chair of WorKer 2011, the Third Workshop on Kernelization, Vienna, Austria, September 2-4, 2011.
  • Program commitee member of SAT 2011, the Fourteenth International Conference on Theory and Applications of Satisfiability Testing June 19-22, 2011, Ann Arbor, USA.
  • Program committee member of NECTAR 2011, Special Track on New Scientific and Technical Advances in Research; part of AAAI 2011, Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, USA, August 7-11, 2010.
  • Chair of PCCR 2010, the first workshop on the Parameterized Complexity of Computational Reasoning, Satellite Workshop of the federated MFCS & CSL 2010 conference, Brno, Czech Republic, 28 August 2010.
  • Co-chair of SAT 2010, Thirteenth International Conference on Theory and Applications of Satisfiability Testing, July 11-14, 2010, Edinburgh, UK, part of FLOC 2010, The Federated Logic Conference 2010.
  • Program committee member of MFCS 2010, 35th International Symposium on Mathematical Foundations of Computer Science, Brno, Czech Republic, August 23-27, 2010.
  • Program committee member of ISAIM 2010, 11th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, January 6-8, 2010.
  • Program committee member of NECTAR 2010, Special Track on New Scientific and Technical Advances in Research; part of AAAI 2010, Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, Georgia, USA, July 11-15, 2010.
  • Program committee member of IWPEC 2009, 4th International Workshop on Parameterized and Exact Computation, 10-11 September 2009, IT University of Copenhagen, Denmark. Part of ALGO 2009.
  • Program committee member of IJCAI 2009, Twenty-First International Joint Conference on Artificial Intelligence, July 11-17, 2009, Pasadena, California, USA.
  • Program committee member of SAT 2009, Twelfth International Conference on Theory and Applications of Satisfiability Testing, 30 June - 3 July 2009, Swansea, Wales, United Kingdom.
  • Program committee member of CATS 2009, Computing: The Australasian Theory Symposium, Wellington, New Zealand, January 20-23, 2009. Part of ASCW 2009, the Australasian Computer Science Week 2009.
  • Program committee member of IWPEC 2008, Third International Workshop on Exact and Parameterized Computation, May 14-16, 2008, Victoria (BC), Canada. Colocated with STOC 2008.
  • Program committee member of AAAI 2008, Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, Illinois, USA, July 13-17, 2008.
  • Program committee member of SAT 2008, Eleventh International Conference on Theory and Applications of Satisfiability Testing, May 12-15, 2008, Guangzhou, P. R. China.
  • Co-organizer of ACiD 2007, Third Workshop on Algorithms and Complexity in Durham, September 17-19, 2007, University of Durham, England, UK.
  • Program committee member of SAT 2007, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 28-31, 2007, Lisbon, Portugal.
  • Co-organizer of ACiD 2006, Second Workshop on Algorithms and Complexity in Durham, September 18-20, 2006, University of Durham, England, UK.
  • Program committee member of SAT 2006, Ninth International Conference on Theory and Applications of Satisfiability Testing, August 12-15, 2006, Seattle, Washington, USA, affiliated to FLOC 2006.
  • Program committee member of WADS 2005, The Workshop on Algorithms and Data Structures, August 15-17, 2005, University of Waterloo, Waterloo, Canada.
  • Program committee member of SAT 2005, Eighth International Conference on Theory and Applications of Satisfiability Testing, June 19-23, 2005, University of St. Andrews, St. Andrews, Scotland, UK.
  • Co-organizer of ACiD 2005, First Workshop on Algorithms and Complexity in Durham, July 8-10, 2005, University of Durham, England, UK.

Invited Talks

(Selection)
  • Invited tutorial speaker at LI 2012, Logic and Interactions, Complexity Winter School, CIRM Marseille, France, 30 January - 3 February 2012.
  • Invited plenary speaker at INAP 2011/WLP 2011, The 19th International Conference on Applications of Declarative Programming and Knowledge Management, and The 25th Workshop on Logic Programming, Vienna, Austria, 28-30 September 2011.
  • Invited plenary speaker at JFPC/JIAF 2011, the 7th French Conference on Constraint Programming and the 5th French Conference on Artificial Intelligence, Lyon, France, 8-10 June, 2011.
  • Invited speaker at ARW 2009, the Automated Reasoning Workshop 2009, Department of Computer Science, University of Liverpool, UK, 21-22 April 2009.
  • Invited speaker at ICDM 2008, International Conference on Discrete Mathematics, Mysore, India, 6-10 June 2008.
  • Invited speaker at SymCon'07, Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, satellite workshop of CP 2007, Providence, RI, USA, 23 September 2007.

Publications

Journal Papers | Conference Papers | Technical Reports | Book Sections | Volumes Edited

Most of my papers are also listed at the DBLP Computer Science Bibliography. My Erdös Number is 2.

Journal Papers

  1. Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo. Algorithmica, to appear. Preliminary version appeared in the proceedings of IPEC 2010.
  2. On Contracting Graphs to Fixed Pattern Graphs. Pim van't Hof, Marcin Kaminski, Daniel Paulusma, Stefan Szeider and Dimitrios M. Thilikos. Discrete Applied Mathematics, to appear.
  3. Editing Graphs to Satisfy Degree Constraints: A Parameterized Approach. Luke Mathieson and Stefan Szeider. J. of Computer and System Sciences, vol. 78, no. 1, pp. 179-191, 2012.
  4. Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 61, no. 3, 2011, pp. 638-655. Preliminary version appeared in SODA 2010.
  5. Parameterized Proof Complexity. Stefan Dantchev, Barnaby Martin, and Stefan Szeider. Computational Complexity, vol. 20, no. 1, pp. 51-85. A preliminary version appeared in the proceedings of FOCS 2007.
  6. Algorithms and Complexity Results for Persuasive Argumentation. Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. Artificial Intelligence, vol. 175, pp. 1722-1736, 2011.
  7. Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. ACM Transactions on Computational Logic, vol. 12, no. 2, article 12, 2011.
  8. The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Discrete Optimization, vol. 8, pp. 139-145, 2011.
  9. A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. J. Computer and System Sciences, vol. 77, no. 2, pp. 422-429, 2011.
  10. Tractable Cases of the Extended Global Cardinality Constraint. Marko Samer and Stefan Szeider. Constraints, vol. 16, no. 1, pp. 1-24, 2011.
  11. On the Complexity of Some Colorful Problems Parameterized by Treewidth. M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, C. Thomassen. Information and Computation, vol. 209, no. 2, pp. 143-153, 2011.
  12. Algorithms for Propositional Model Counting. Marko Samer and Stefan Szeider. J. of Discrete Algorithms, vol. 8, no. 1, pp. 50-64, 2010.
  13. Constraint Satisfaction with Bounded Treewidth Revisited. Marko Samer and Stefan Szeider. J. of Computer and System Sciences, vol. 76, no. 2, pp. 103-114, 2010.
  14. Clique-Width is NP-Complete. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. SIAM Journal on Discrete Mathematics vol. 23, no. 2, pp. 909-939, 2009. A preliminary and shortened version of this paper appeared in STOC'06.
  15. Covering Graphs with Few Complete Bipartite Subgraphs. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Theoretical Computer Science, vol. 410, no. 21-23, pp. 2045-2053, 2009.
  16. Backdoor Sets of Quantified Boolean Formulas. Marko Samer and Stefan Szeider. Journal of Automated Reasoning, vol. 42, no. 1, pp. 77-97, 2009.
  17. Fixed-Parameter Complexity of Minimum Profile Problems. Gregory Gutin, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 52, no. 2, pp. 133-152, 2008.
  18. Matched Formulas and Backdoor Sets. Stefan Szeider. Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, pp. 1-12, 2008.
  19. Fixed-Parameter Algorithms for Artificial Intelligence, Constraint Satisfaction, and Database Problems. Georg Gottlob and Stefan Szeider. The Computer Journal, vol. 51, no. 3, pp. 303-325, 2008.
  20. Solving #SAT Using Vertex Covers. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Acta Informatica, vol. 44, no. 7-8, pp. 509-523, 2007.
  21. The Linear Arrangement Problem Parameterized Above Guaranteed Value. Gregory Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. Theory of Computing Systems, vol. 41, pp. 521-538, 2007.
  22. A note on unsatisfiable k-CNF formulas with few occurrences per variable. Shlomo Hoory and Stefan Szeider. SIAM Journal on Discrete Mathematics, vol. 20, no. 2, pp. 523-528, 2006.
  23. On Finding Short Resolution Refutations and Small Unsatisfiable Subsets. Michael R. Fellows, Stefan Szeider, and Graham Wrightson. Theoretical Computer Science, vol. 351, no. 3, pp. 351-359, 2006.
  24. On Edge-Colored Graphs Covered by Properly Colored Cycles. Herbert Fleischner and Stefan Szeider. Graphs and Combinatorics, vol. 21, no. 3, pp. 301-306, 2005.
  25. Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable. Shlomo Hoory and Stefan Szeider. Theoretical Computer Science, vol. 337, no. 1-3, pp. 347-359, 2005.
  26. Backdoor Sets for DLL Subsolvers. Stefan Szeider. Journal of Automated Reasoning, vol. 35, no. 1-3, pp.73-88, 2005. Reprinted as Chapter 4 of the book SAT 2005 - Satisfiability Research in the Year 2005, edited by E. Giunchiglia and T. Walsh, Springer Verlag, 2006.
  27. The Complexity of Resolution with Generalized Symmetry Rules. Stefan Szeider. Theory of Computing Systems, vol. 38, no. 2, pp. 171-188, 2005.
  28. Generalizations of Matched CNF Formulas. Stefan Szeider. Annals of Mathematics and Artificial Intelligence, vol. 43, No. 1-4, pp. 223-238, 2005.
  29. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Stefan Szeider. J. of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, 2004.
  30. On Theorems Equivalent with Kotzig's Result on Graphs with Unique 1-Factors. Stefan Szeider. Ars Combinatoria, vol. 73, pp. 53-64, 2004.
  31. Homomorphisms of Conjunctive Normal Forms. Stefan Szeider. Discrete Applied Mathematics, vol. 130 no. 2, pp. 351-365, 2003.
  32. Finding Paths in Graphs Avoiding Forbidden Transitions. Stefan Szeider. Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 239-251, 2003.
  33. Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference. Herbert Fleischner, Oliver Kullmann, and Stefan Szeider. Theoretical Computer Science, vol. 289, no. 1, pp. 503-516, 2002.

Conference Papers

Conference papers are only listed if there is not a corresponding journal paper.

  1. k-Gap Interval Graphs. Fedor V. Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, and Yngve Villanger. Proceedings of LATIN 2012, The 10th Latin American Theoretical Informatics Symposium, April 16-20, 2012, Arequipa, Peru. Lecture Notes in Computer Science, Springer, 2012, to appear.
  2. The Parameterized Complexity of Local Consistency. Serge Gaspers and Stefan Szeider. Proceedings of CP 2011, Principles and Practice of Constraint Programming, 17th International Conference, Perugia, Italy, September 12-16, 2011. pp 302-316, Lecture Notes in Computer Science vol. 6876, Springer, 2011.
  3. Limits of Preprocessing. Stefan Szeider. Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI 2011), pp. 93-98, AAAI Press, Menlo Park, California, 2011.
  4. Kernels for Global Constraints. Serge Gaspers and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 540-545, 2011.
  5. Augmenting Tractable Fragments of Abstract Argumentation. Sebastian Ordyniak and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 1033-1038, 2011.
  6. Backdoors to Tractable Answer-Set Programming. Johannes Klaus Fichte and Stefan Szeider. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2011), AAAI Press/IJCAI, pp. 863-868, 2011.
  7. Satisfiability of Acyclic and Almost Acyclic CNF Formulas (II). Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of SAT 2011, Fourteenth International Conference on Theory and Applications of Satisfiability Testing June 19-22, 2011, Ann Arbor, USA. Lecture Notes in Computer Science vol. 6695, pp. 47-60, Springer, 2011.
  8. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Proceedings of FSTTCS 2010, 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), pp. 84-95, 2010.
  9. Reasoning in Argumentation Frameworks of Bounded Clique-Width. Wolfgang Dvovrak, Stefan Szeider, and Stefan Woltran. Proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 219-230.
  10. Algorithms and Complexity Results for Exact Bayesian Structure Learning. Sebastian Ordyniak and Stefan Szeider. Proceedings of UAI 2010, The 26th Conference on Uncertainty in Artificial Intelligence, Catalina Island, California, USA, July 8-11, 2010. Peter Grünwald and Peter Spirtes (eds.), AUAI Press, Corvallis, pp. 401-408, 2010.
  11. Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough. Reinhard Pichler, Stefan Rümmele, Stefan Szeider and Stefan Woltran. Proceedings of KR 2010, Twelfth International Conference on Principles of Knowledge Representation and Reasoning Toronto, Canada, May 9-13, 2010, AAAI Press 2010.
  12. Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Invited Talk. Seclected and revised papers of ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India. RMS Lecture Notes Series no. 13, pp. 179-190. Ramanujan Mathematical Society, 2010
  13. Backdoor Trees. Marko Samer and Stefan Szeider. Proceedings of AAAI 2008, Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, Illinois, USA, July 13-17, 2008, pp. 363-368, AAAI Press, 2008.
  14. Without Loss of Generality -- Symmetric Reasoning for Resolution Systems. Stefan Szeider. Invited talk. Proceedings of SymCon'07, Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, satellite workshop of CP 2007, September 23, 2007, Providence, RI, USA, pp. 5-8, 2007.
  15. Detecting Backdoor Sets with Respect to Horn and Binary Clauses. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004).
  16. On Fixed-parameter Tractable Parameterizations of SAT. Stefan Szeider. Theory and Applications of Satisfiability (Selected and Revised Papers of SAT 2003) Lecture Notes in Computer Science 2919, pp. 188-202, 2004.
  17. NP-Completeness of Refutability by Literal-Once Resolution. Stefan Szeider. Proceedings IJCAR 2001, Lecture Notes in Artificial Intelligence 2083, pp.168-181, 2001.

Technical Reports

Technical reports are only listed if there is not a corresponding conference or journal publication.

  1. Backdoors to Acyclic SAT. Serge Gaspers and Stefan Szeider. Technical Report, Arxiv.org: 1110.6384, October 2011.
  2. Backdoors to Satisfaction. Serge Gaspers and Stefan Szeider. Survey paper. Arxiv.org: 1110.6387, October 2011.

Book Sections

  1. Parameterized SAT. Stefan Szeider. In Encyclopedia of Algorithms, edited by Ming-Yang Kao, Springer Verlag, 2008.
  2. Fixed-parameter Tractability. Marko Samer and Stefan Szeider. Chapter 13 of the Handbook of Satisfiability, edited by A. Biere, M. Heule, H. van Maaren, and T. Walsh. IOS Press, 2009.

Volumes Edited

  1. SAT 2010, Proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing. Ofer Strichman and Stefan Szeider (eds.). Lecture Notes in Computer Science, Volume 6175, Springer Verlag 2010.
  2. Algorithms and Complexity in Durham 2007, Proceedings of the Third ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson, and Stefan Szeider (eds.). Texts in Algorithmics 9, College Publications, London, 2007. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 8, Issue 2, June 2010) with selected papers from ACiD 2007.
  3. Algorithms and Complexity in Durham 2006, Proceedings of the Second ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson and Stefan Szeider (eds.). Texts in Algorithmics 7, College Publications, London, 2006. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 7, Issue 2, June 2009) with selected papers from ACiD 2006.
  4. Algorithms and Complexity in Durham 2005, Proceedings of the First ACiD Workshop. Hajo Broersma, Stefan Dantchev, Matthew Johnson, and Stefan Szeider (eds.). Texts in Algorithmics 4, King's College Publications, London, 2005. We guest-edited a special issue of the Journal of Discrete Algorithms (Volume 6, Issue 4, 2008) with selected papers from ACiD 2005.



Vienna Center for Logic and Algorithms

Official Opening
January 25, 2011



What means "it's intractable"?

Professor's Portrait
(in German)
December 20, 2011



WorKer 2011

Third Workshop on Kernelization
Vienna, Austria,
September 2-4, 2011



Parameterized Complexity of Computational Reasoning

Satellite Workshop of MFCS & CSL 2010, Brno, Czech Republic, August 28, 2010



SAT 2010 at FLoC 2010

13th International Conference on Theory and Applications of Satisfiability Testing, July 11-July 14, 2010, Edinburgh, UK



Inaugural Lecture

My inaugural lecture as Professor of Discrete Reasoning Methods, Vienna University of Technology, May 26, 2010



TU News, Nov. 4, 2009

"Two ERC grants for researchers of the Faculty of Informatics."




Handbook of Satisfiability, IOS Press, 2009. Chapter 13: Fixed-Parameter Tractability, Marko Samer and Stefan Szeider