Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Seminar on CSP - NMAG573

Title:	Seminář k problému CSP
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
Semester:	both
E-Credits:	3
Hours per week, examination:	0/2, C [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time
Note:	you can enroll for the course repeatedly you can enroll for the course in winter and in summer semester

Guarantor:	doc. Mgr. Libor Barto, Ph.D. Michael Pinsker, dipl. ing.
Class:	M Mgr. MMIB M Mgr. MMIB > Volitelné M Mgr. MSTR M Mgr. MSTR > Volitelné
Classification:	Mathematics > Algebra

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KA (14.05.2013)

The seminar is a continuation of the course NALG117 (Introduction to the complexity of the CSP). According to partincipants' interest we focus on selected deeper results, for example the dichotomy for conservative CSPs, the dichotomy for CSPs on a three-element set, few subpowers CSPs, the dichotomy for smooth digraphs or characterization of bounded width problems.

Literature -

Last update: T_KA (14.05.2013)

[1] L. Barto, M. Kozik: Constraint Satisfaction Problems of Bounded Width. manuscript, 2009.

[2] L. Barto, M. Kozik, T. Niven: Graphs, polymorphisms and the complexity of homomorphism problems. In STOC'08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 789-796, New York, NY, USA, 2008.

[3] A. Bulatov: Tractable conservative constraint satisfaction problems. In LICS 03: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, page 321, Washington, DC, USA, 2003. IEEE Computer Society.

[4] A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006.

[5] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.

[6] T. Feder, M.Y. Vardi: The computational structure of monotonie monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.

[7] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard: Tractability and learnability arising from algebras with few subpowers, pp. 213-224, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

[8] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.

Syllabus -

Last update: T_KA (14.05.2013)

Participants present selected articles concerning CSP.