Time: 1:30pm -, November 2
Place: Room E1011, W8 building, Tokyo Institute of Technology

Speaker: Laszlo Egri (McGill Univ.)
Title: The Complexity of the List Homomorphism Problem for Graphs
Abstract: 
We completely classify the computational complexity of the list
H-colouring problem for graphs (with possible loops) in combinatorial
and algebraic terms: for every graph H, the problem is either
NP-complete, NL-complete, L-complete or is first-order definable;
descriptive complexity equivalents are given as well via Datalog and
its fragments. Our algebraic characterisations match important
conjectures in the study of constraint satisfaction problems.

Speaker: Yuichi Yoshida (NII & PFI)
Title: An Algebraic Characterization of Testable Boolean CSPs
Abstract: 
Given an instance I of a CSP, a tester for I distinguishes assignments satisfying I 
from those which are far from any assignment satisfying I. 
The efficiency of a tester is measured by its query complexity, 
the number of variable assignments queried by the algorithm. 
In this paper, we characterize the hardness of testing Boolean CSPs 
in terms of the algebra generated by the relations used to form constraints. 
In terms of computational complexity, we show that if a non-trivial Boolean CSP 
is sublinear-query testable (resp., not sublinear-query testable), then the CSP is in NL 
(resp., P-complete, ⊕L-complete or NP-complete) and that if a sublinear-query testable
Boolean CSP is constant-query testable (resp., not constant-query testable), 
then counting the number of so- lutions of the CSP is in P (resp., #P-complete).

Also, we conjecture that a CSP instance is testable in sublinear time 
if its Gaifman graph has bounded treewidth. 
We confirm the conjecture when a near-unanimity operation is a polymorphism of the CSP.


Contact: Akinori Kawachi (Tokyo Institute of Technology)