Publications

Notes on Recognitions

List H-Coloring a Graph by Removing Few Vertices
Rajesh Chitnis, László Egri, Dániel Marx
Recognition: ESA 2013 Best Paper Award (Co-winner)

The Complexity of the List Homomorphism Problem for Graphs
László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
Recognition: The STACS 2010 paper (see Computational Complexity Theory section below) was selected as one of the best conference submissions. Our paper was one of six invited to be extended into a full journal version and was published in a Special Issue of Theory of Computing; this extended version was also included in the Computing Reviews list of 91 notable computing items published in 2012.

Neural Networks, Computer Vision, Cognitive Science

• RainbowTag: a Fiducial Marker System with a New Color Segmentation Algorithm
  László Egri, Hamid Nabati, Jia Yuan Yu
  ICCVE 2022: 1–6

• Constraint-Satisfaction Models
  Egri, L., Shultz, T. R.
  In James D. Wright (editor), International Encyclopedia of the Social & Behavioral Sciences, 2nd ed., Vol. 4, Oxford: Elsevier, pp. 716–723, 2015 (Invited article)

• Could knowledge-based neural learning be useful in developmental robotics? The case of KBCC
  Shultz, T. R., Rivest, F., Egri, L., Thivierge, J-P., & Dandurand, F.
  International Journal of Humanoid Robotics, 4(2): 245–279, 2007

• A compositional neural-network solution to prime-number testing
  Egri, L., & Shultz, T. R.
  Proceedings of the 28th Annual Conference of the Cognitive Science Society (CogSci), 1263–1268, 2006 (Poster presentation)

• Knowledge-based learning with KBCC
  Shultz, T. R., Rivest, F., Egri, L., & Thivierge, J-P.
  Proceedings of the 5th IEEE International Conference on Development and Learning (ICDL), 2006

Computational Complexity Theory

• Parameterized Intractability of Even Set and Shortest Vector Problem
  Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
  J. ACM 68(3): 16:1–16:40, 2021

• Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization
  László Egri, Dániel Marx, Pawel Rzazewski
  STACS 2018: 27:1–27:15

• List H-Coloring a Graph by Removing Few Vertices
  Rajesh Chitnis, László Egri, Dániel Marx
  Algorithmica 78(1): 110–146, 2017

• Fixed-Parameter Approximability of Boolean MinCSPs
  Édouard Bonnet, László Egri, Dániel Marx
  ESA 2016: 18:1–18:18

• On Maltsev Digraphs
  Catarina Carvalho, László Egri, Marcel Jackson, Todd Niven
  Electron. J. Comb. 22(1): 1, 2015

• Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
  Víctor Dalmau, László Egri, Pavol Hell, Benoît Larose, Arash Rafiey
  LICS 2015: 487–498

• Space Complexity of List H-Coloring: a Dichotomy
  László Egri, Pavol Hell, Benoît Larose, Arash Rafiey
  SODA 2014: 349–365

• On Constraint Satisfaction Problems Below P
  László Egri
  J. Log. Comput. 26(3): 893–922, 2014

• List H-Coloring a Graph by Removing Few Vertices
  Rajesh Chitnis, László Egri, Dániel Marx
  ESA 2013: 313–324 (Co-winner of the ESA 2013 Best Paper Award)

• The Complexity of the List Homomorphism Problem for Graphs
  László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
  Theory of Computing Systems (Special Issue) 51(2): 143–178, 2012
  (The STACS 2010 paper was selected as one of the best conference submissions. Our paper was one of six invited to be extended into a full journal version and was published in a Special Issue of Theory of Computing; this extended version was also included in the Computing Reviews list of 91 notable computing items published in 2012.)

• On Constraint Satisfaction Problems Below P
  László Egri
  CSL 2011: 203–217

• On Maltsev Digraphs
  Catarina Carvalho, László Egri, Marcel Jackson, Todd Niven
  CSR 2011: 181–194

• The Complexity of the List Homomorphism Problem for Graphs
  László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
  STACS 2010: 335–346

• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
  László Egri, Benoît Larose, Pascal Tesson
  ICALP 2008: 172–183

• Symmetric Datalog and Constraint Satisfaction Problems in Logspace
  László Egri, Benoît Larose, Pascal Tesson
  LICS 2007: 193–202

Theses

• The Fine-Grained Complexity of Constraint Satisfaction Problems
  PhD thesis, McGill University, 2012

• The Complexity of Constraint Satisfaction Problems and Symmetric Datalog
  Master’s thesis (Dean’s Honour List), McGill University, 2007

Unpublished Manuscript

• Space Complexity of List H-Coloring Revisited: The Case of Oriented Trees
  L. Egri
  arXiv:1510.07124 [cs.CC], 2015