George Katsirelos

Research

Software

• Minicsp is a clause learning CSP solver that I developed based on the ideas in my thesis (see [Katsirelos and Bacchus, AAAI-2005], or my thesis).
• GlucosER is a CDCL (conflict-driven clause learning) SAT solver that uses a restriction of extended resolution. The objective is to get significant speedups in some instances due to the more powerful proof system, without sacrificing performance compared to current CDCL solvers. For more, see [Audemard, Katsirelos and Simon, AAAI-2010]. Download the source tarball of glucosER 1.0 or get a statically linked linux 32-bit binary. Note that you need boost to compile glucosER.

Conference papers

1. Detecting and Exploiting Subproblem Tractability. Christian Bessiere,Clement Carbonnel, Emmanuel Hebrard, George Katsirelos and Toby Walsh. Proceedings of IJCAI 2013.
2. Constraint Acquisition via Partial Queries. Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of IJCAI 2013.
3. Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers. George Katsirelos, Ashish Sabharwal, Horst Samulowitz and Laurent Simon. Proceedings of AAAI 2013.
4. The SeqBin constraint revisited. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CP 2012. An extended version of this, including all proofs, is available on arxiv.
5. Computational Protein Design as a Cost Function Network Optimization Problem. David Allouche, Seydou Traoré, Isabelle André, Simon de Givry, George Katsirelos, Sophie Barbe and Thomas Schiex. Proceedings of CP 2012.
6. Eigenvector centrality in industrial SAT instances. George Katsirelos and Laurent Simon. Proceedings of CP 2012.
7. Learning Polynomials over GF(2) in a SAT Solver (Poster Presentation). George Katsirelos, Laurent Simon. Proceedings of SAT 2012, LNCS 7317, 496--497, 2012. Published version.
8. Complexity of and Algorithms for Borda Manipulation. Jessica Davies, George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of AAAI-2011, 2011. Published version. Outstanding paper award
9. Decomposition of the NValue Constraint. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of CP-2010, LNCS 6308, 114--128, 2010. Published version.
10. On The Complexity and Completeness of Static Constraints for Breaking Row and Column Symmetry. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CP-2010, LNCS 6308, 305--320, 2010. Published version.
11. Symmetries of Symmetry Breaking Constraints. George Katsirelos, Toby Walsh. Proceedings of ECAI-2010, 861--866, 2010. Published version.
12. A Restriction of Extended Resolution for Clause Learning SAT Solvers. Gilles Audemard, George Katsirelos and Laurent Simon. Proceedings of AAAI-2010, 15-20, 2010. Published version.
13. Propagating Conjunctions of AllDifferent Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of AAAI-2010, 27-32, 2010. Published version.
14. Restricted Global Grammar Constraints. George Katsirelos, Sebastian Maneth, Nina Narodytska and Toby Walsh. Proceedings of CP-2009, LNCS 5732, 501-508, 2009. Published version.
15. Circuit Complexity and Decompositions of Global Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of IJCAI-2009, 2009. Published version.
16. Decompositions of All Different, Global Cardinality and Related Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of IJCAI-2009, 2009. Published version.
17. Reformulating Global Grammar Constraints. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CPAIOR-2009, LNCS 5547, 132-147, 2009. Published version.
18. Combining Symmetry Breaking and Global Constraints. George Katsirelos, Nina Narodytska, and Toby Walsh. "Recent Advances in Constraints", Post-conference proceedings of CSCLP-2008, LNAI 5655, 2009. Published version.
19. The Weighted CFG Constraint. George Katsirelos, Nina Narodytska and Toby Walsh, Proceedings of CP-AI-OR 2008, LNCS 5015, 323-327, 2008. Published version.
20. A Compression Algorithm for Large Arity Extensional Constraints. George Katsirelos and Toby Walsh, Proceedings of CP-2007, LNCS 4741, 379-393, 2007. Published version.
21. Generalized Nogoods in CSPs. George Katsirelos and Fahiem Bacchus, The twentieth national conference on artificial intelligence -- AAAI-05. Published version.
22. Unrestricted Nogood Recording in CSP search. George Katsirelos and Fahiem Bacchus, Ninth International Conference on Principles and Practice of Constraint Programming--CP 2003. Extended version. Published version.
23. GAC on conjunctions of constraints. G. Katsirelos and F. Bacchus, Principles and Practice of Constraint Programming--CP 2001, pages 610--614, 2001. Published version

Journal papers

1. The Complexity of Integer Bound Propagation. Lucas Bordeaux, George Katsirelos, Nina Narodytska and Moshe Y. Vardi. In Journal of Artificial Intelligence Research (JAIR), 40, 657--676, 2011. Published version.
2. The Weighted Grammar Constraint. George Katsirelos, Nina Narodytska and Toby Walsh. Annals of Operations Research, 2010. Published version

Selected Workshop papers

1. An Empirical Study of Borda Manipulation. Jessica Davies, George Katsirelos, Nina Narodytska and Toby Walsh. Third International Workshop on Computational Social Choice, COMSOC-2010, 2010. (link)
2. Two Encodings of DNNF Theories. Jean Christoph Jung, Pedro Barahona, George Katsirelos and Toby Walsh. ECAI'08 Workshop on Inference methods based on Graphical Structures of Knowledge, 2008. (link)

Thesis