(I have joined the Vienna University of Technology, Austria,
my homepage will move in a couple of days ...)

2004-2009: Durham University, Durham, United Kingdom
2002-2004: University of Toronto, Toronto, Canada
1999-2002: Austrian Academy of Sciences, Vienna, Austria

Contact

Dr Stefan Szeider
School of Engineering and Computing Sciences, Durham University
Science Labs, South Road, Durham DH1 3LE, England, UK
office location: CS 3.09 (level 3)
phone: ++44 191 3341 759 | fax: ++44 191 3341 701
e-mail: <first name>@<last name>.net
web: http://www.szeider.net

Research Interests

My work deals with the computational complexity of problems and their algorithmic solution. In particular I am interested in problems for which there is a strong theoretical evidence of intractability, but which may admit efficient solutions for special cases. 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. The ultimate goal is to understand the question: What makes a problem hard? Along these lines I have considered the boolean satisfiability problem (SAT), quantified boolean formulas (QBF), constraint satisfaction problems (CSP), and problems in graphs and networks.

Recent Invited Talks

  • 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 the Department of Computer Science, Royal Holloway, University of London, Computer Science Seminar, 24 February 2009.
  • Invited speaker at Institute for Information Systems, Databases and Artificial Intelligence group, DBAI Seminar, Vienna Technical University, Vienna, Austria, 22 January 2009.
  • Invited speaker at Laboratoire d'Algorithmique et Image de Clermont-Ferrand, Seminar LAIC, Universite d'Auvergne, France, 13 November 2008.
  • Invited speaker at Center for Discrete Mathematics and its Applications (DIMAP), DIMAP Seminar, University of Warwick, UK, 21 October 2008.
  • 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.

Program Committees

  • Co-chair of the Program Committee of SAT 2010, Thirteenth International Conference on Theory and Applications of Satisfiability Testing, July 11-14, 2010, Edinburgh, UK, affiliated to FLOC 2010, The Federated Logic Conference 2010.
    Deadline for Workshop Proposals is July 31, 2009.
  • 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 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.

Publications

Most of my papers are also listed at the DBLP Computer Science Bibliography.
Try DBLP Viz for a visualization of coauthorship.

Journal Papers

  1. Tractable Cases of the Extended Global Cardinality Constraint. Marko Samer and Stefan Szeider. Constraints, to appear.
  2. Algorithms for Propositional Model Counting. Marko Samer and Stefan Szeider. J. of Discrete Algorithms, to appear.
  3. 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.
  4. 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.
  5. Backdoor Sets of Quantified Boolean Formulas. Marko Samer and Stefan Szeider. Journal of Automated Reasoning, vol. 42, no. 1, pp. 77-97, 2009.
  6. Constraint Satisfaction with Bounded Treewidth Revisited. Marko Samer and Stefan Szeider. Journal of Computer and System Sciences, to appear.
  7. Fixed-Parameter Complexity of Minimum Profile Problems. Gregory Gutin, Stefan Szeider, and Anders Yeo. Algorithmica, vol. 52, no. 2, pp. 133-152, 2008.
  8. Matched Formulas and Backdoor Sets. Stefan Szeider. Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, pp. 1-12, 2008.
  9. 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.
  10. Solving #SAT Using Vertex Covers. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Acta Informatica, vol. 44, no. 7-8, pp. 509-523, 2007.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. The Complexity of Resolution with Generalized Symmetry Rules. Stefan Szeider. Theory of Computing Systems, vol. 38, no. 2, pp. 171-188, 2005.
  18. Generalizations of Matched CNF Formulas. Stefan Szeider. Annals of Mathematics and Artificial Intelligence, vol. 43, No. 1-4, pp. 223-238, 2005.
  19. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Stefan Szeider. Journal of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, 2004.
  20. On Theorems Equivalent with Kotzig's Result on Graphs with Unique 1-Factors. Stefan Szeider. Ars Combinatoria, vol. 73, pp. 53-64, 2004.
  21. Homomorphisms of Conjunctive Normal Forms. Stefan Szeider. Discrete Applied Mathematics, vol. 130 no. 2, pp. 351-365, 2003.
  22. Finding Paths in Graphs Avoiding Forbidden Transitions. Stefan Szeider. Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 239-251, 2003.
  23. 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

Papers are listed only if there is not a corresponding journal paper (yet).

  1. Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Proceedings of SODA 2010, the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, January 17-19, 2010, Austin, Texas, USA, to appear.
  2. A Probabilistic Approach to Problems Parameterized Above Tight Lower Bound. Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Proceedings of IWPEC 2009, 4th International Workshop on Parameterized and Exact Computation, 10-11 September 2009, IT University of Copenhagen, Denmark. Part of ALGO 2009. Lecture Notes in Computer Science, Springer, to appear.
  3. The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Stefan Szeider. Proceedings of SAT 2009, Twelfth International Conference on Theory and Applications of Satisfiability Testing, 30 June - 3 July 2009, Swansea, Wales, United Kingdom. Lecture Notes in Computer Science, vol. 5584, Springer-Verlag, 2009, to appear.
  4. Monadic Second Order Logic on Graphs with Local Cardinality Constraints. Stefan Szeider. Proceedings of MFCS 2008, 33rd International Symposium on Mathematical Foundations of Computer Science 25-29 August 2008, Torun, Poland. Lecture Notes in Computer Science, vol. 5162, pp. 601-612, Springer-Verlag, 2008.
  5. Not So Easy Problems For Tree Decomposable Graphs. Stefan Szeider. Invited Talk. Proceedings of ICDM 2008, International Conference on Discrete Mathematics, June 6-10, 2008, Mysore, India, pp. 161-171.
  6. Parameterized Graph Editing with Chosen Vertex Degrees. Luke Mathieson and Stefan Szeider. Proceedings of COCOA 2008, 2nd Annual International Conference on Combinatorial Optimization and Applications, August 21-24, 2008, in St. John's, Newfoundland, Canada. Lecture Notes in Computer Science, vol. 5165, pp. 13-22, Springer-Verlag, 2008.
  7. 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.
  8. The Parameterized Complexity of Regular Subgraph Problems and Generalizations. Luke Mathieson and Stefan Szeider. Proceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008, part of the Australasian Computer Society Week (ACSW 2008), CRPIT vol. 77, pp. 79-86, Australian Computer Society, 2008.
  9. Parameterized Proof Complexity. Stefan Dantchev, Barnaby Martin, and Stefan Szeider. FOCS 2007, The 48th Annual Symposium on Foundations of Computer Science, October 20-23, 2007, Providence, RI, USA, pp. 150-160, IEEE Press, 2007.
  10. 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.
  11. On the Complexity of Some Colorful Problems Parameterized by Treewidth. (invited paper) M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, C. Thomassen. Proceedings of COCOA 2007, The First International Conference on Combinatorial Optimization and Applications, August 12-15, 2007, Xi'an, Shaanxi, China. Lecture Notes in Computer Science, vol. 4616, pp. 366-377, 2007.
  12. 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).
  13. 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.
  14. NP-Completeness of Refutability by Literal-Once Resolution. Stefan Szeider. Proceedings IJCAR 2001, Lecture Notes in Artificial Intelligence 2083, pp.168-181, 2001.

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. 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.
  2. 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.
  3. 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.

Technical Reports

  1. Complexity and Applications of Edge-Induced Vertex-Cuts.
    Marko Samer and Stefan Szeider. Arxiv.org preprint archive, Report cs.DM/0607109, July 2006.





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