Course Page

Syllabus

Assignments

Resources

Campus Policies

Important Dates

• Barto, Libor; Kozik, Marcin
  Constraint Satisfaction Problems Solvable by Local Consistency Methods.
  Journal of the ACM, 61 (2014), Issue 1, Article No. 3.
• Barto, L.; Kozik, M.; Niven, T.
  The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell).
  SIAM Journal on Computing 38/5 (2009), 1782-1802.
• van Benthem, Johan; Doets, Kees
  Higher-order logic.
  Handbook of philosophical logic, Vol. 1, 189-243, Kluwer Acad. Publ., Dordrecht, 2001.
• Berman, J.; Idziak, P.; Markovic, P.; McKenzie, R.; Valeriote, M. Willard, R.
  Varieties with few subalgebras of powers.
  Trans. Amer. Math. Soc. 362 (2010), 1445-1473.
• Bodirsky, Manuel
  Cores of countably categorical structures.
  Log. Methods Comput. Sci. 3 (2007), no. 1, 1:2, 16 pp.
• Bodirsky, Manuel
  Constraint Satisfaction Problems with Infinite Templates.
  Survey, in LNCS 5250, Complexity of Constraints - An Overview of Current Research Themes.
  Creignou, N., Kolaitis, P.G., Vollmer, H. (Eds.)
  pp. 196-228, 2008, ISBN 978-3-540-92799-0.
• Bodirsky, Manuel; Kara, Jan
  The complexity of temporal constraint satisfaction problems.
  Journal of the ACM, 57 (2010), Issue 2, Article No. 9.
• Bodirsky, Manuel; Pinsker, Michael
  Reducts of Ramsey structures.
  in: Contemporary Mathematics, vol. 558, American Mathematical Society, 2011; pp. 489-519.
• Bodirsky, Manuel; Pinsker, Michael
  Schaefer's theorem for graphs.
  Preprint.
• Bulatov, Andrei
  A dichotomy theorem for constraint satisfaction problems on a 3-element set.
  Journal of the ACM 53 (2006), Issue 1, 66-120.
• Bulatov, Andrei
  Complexity of conservative constraint satisfaction problems.
  ACM Transactions in Computational Logic 12 (4), 2011, paper 24.
• Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
  Classifying the complexity of constraints using finite algebras.
  SIAM J. Comput. 34 (2005), no. 3, 720 - 742.
• Fagin, Ronald
  Generalized first-order spectra and polynomial-time recognizable sets.
  Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973),
  pp. 43-73. SIAM-AMS Proc., Vol. VII, Amer. Math. Soc., Providence, R.I., 1974.
• Feder, Tomás; Vardi, Moshe Y.
  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.
  SIAM J. Comput. 28 (1999), no. 1, 57-104 (electronic).
• Hillebrand, G. G.; Kanellakis, P. C.; Mairson, H. G.; Vardi, M. Y.;
  Tools for Datalog boundedness.
  PODS '91 Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp. 1-12.
• Hopcroft, John E.; Ullman, Jeffrey D.
  Introduction to automata theory, languages, and computation
  1979.
  Engineering, Math, Physics Library--Stacks (Call number: QA267 .H56)
• Idziak, P.; Markovic, P.; McKenzie, R.; Valeriote, M. Willard, R.
  Tractability and learnability arising from algebras with few subpowers.
  SIAM J. Comput. 39 no. 7 (2010), 3023-3037 (electronic).
• Kozik, M.; Krokhin, A.; Valeriote, M.; Willard, R.
  Characterizations of several Maltsev conditions.
  Preprint, 2014.
• Kearnes, Keith A.; Markovic, Petar; McKenzie, Ralph N.
  Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
  Algebra Universalis 72 (2014), no. 1, 91 - 100.
• Kun, Gabor
  Constraints, MMSNP and expander relational structures.
  Combinatorica 33 (2013), no. 3, 335 - 347.
• Kun, Gabor; Nesetril, Jaroslav
  Forbidden lifts (NP and CSP for combinatorialists).
  European J. Combin. 29 (2008), no. 4, 930 - 945.
• Pippenger, N.; Fischer, M. J.
  Relations Among Complexity Measures.
  Journal of the ACM 26 (1979), 361 - 381.
• Schaefer, Thomas J.
  The Complexity of Satisfiability Problems.
  STOC 1978. pp. 216-226.
• Szendrei, A
  The Galois Connection between Operations and Relations.
  (unpublished notes)
• Two Proofs of Ladner's Theorem.