László Egri's Home Page

 

Interests:

 

I am a postdoc at the Hungarian Academy of Sciences - Institute for Computer Science and Control (MTA SZTAKI). I am interested in complexity theory, mostly in the complexity of constraint satisfaction problems.

 

Contact Info:

 

Email: laszlo dot egri at mail dot mcgill dot ca (OR egri dot laszlo at sztaki dot mta dot hu)

Address: Lágymányosi utca 11, Budapest, 1111, Hungary

Room number: L 411

Phone: +36 1 279 6169
Department:
Research Group for Parameterized Algorithms and Complexity

Publications (Note that the usual copyright restrictions apply for the information provided below.)

Theory of Computation:

1.     L. Egri, P. Hell, B. Larose, A. Rafiey. Space complexity of list H-coloring: a dichotomy (long version). To appear in SODA 2014.

2.     R. Chitnis, L. Egri, D. Marx. List H-Coloring a Graph by Removing Few Vertices (pdf is long version). To appear in ESA 2013. Co-winner of the ESA 2013 Best Paper Award.

3.     L. Egri. On Constraint Satisfaction Problems below P. Journal of Logic and Computation, 2013. Accepted.

4.     L. Egri, A. Krokhin, B. Larose, P. Tesson. The complexity of the list homomorphism problem for graphs. Special issue of Theory of Computing Systems, 2012. Among top 6 papers at STACS 2010. (And on the best of 2012 list, here.)

5.     L. Egri. On Constraint Satisfaction Problems below P. Conference on Computer Science Logic (CSL), 2011.

6.     C. Carvalho, L. Egri, M, Jackson, T. Niven. On Maltsev Digraphs. International Computer Science Symposium in Russia (CSR), 2011.

7.     L. Egri, A. Krokhin, B. Larose, P. Tesson. The complexity of the list homomorphism problem for graphs, STACS, 2010.

8.     L. Egri, B. Larose, P. Tesson. Directed st-connectivity is not expressible in symmetric Datalog, ICALP, 2008.

9.     L. Egri, B. Larose, P. Tesson. Symmetric Datalog and constraint satisfaction problems in logspace. Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS), 193-202, 2007.

Cognitive Science:

10.  L. Egri, T. R. Shultz. Constraint-satisfaction Models. To appear in the International Encyclopedia of Social and Behavioral Sciences 2nd Eddition, due to be published in 2015. (Invited article.)

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

12.  Egri, L., & Shultz, T. R. (2006). A compositional neural-network solution to prime-number testing. Proceedings of the Twenty-eighth Annual Conference of the Cognitive Science Society (pp. 1263-1268). Mahwah, NJ: Erlbaum.

13.  Shultz, T. R., Rivest, F., Egri, L., & Thivierge, J. P. (2006). Knowledge-based learning with KBCC. Proceedings of the Fifth International Conference on Development and Learning ICDL 2006. Department of Psychological and Brain Sciences, Indiana University, Bloomington, IN.

14.  Egri, L., & Shultz, T. R. (2005). A compositional neural-network solution to primality testing. The Oculus, 2, 10-16.

o U21 Undergraduate Research Conference presentation video.

Master's Thesis (Dean's Honour List)

The Complexity of Constraint Satisfaction Problems and Symmetric Datalog.

Curriculum Vitae (out-of-date)

CV.

 

Last updated: 2013