Barto and Kozik have introduced several weak consistency notions for CSPs, such as ``Prague instances'', ``weak Prague instances'', and ``pq-consistency'', and have shown that any CSP template which can be solved by a local consistency algorithm can also be solved using one of these weak consistency notions. Their definition of ``weak Prague instance'' breaks up into three natural conditions on the directed graph of implications between single-variable restrictions, which they call (P1), (P2), and (P3). (P1) is the standard generalization of arc-consistency to CSPs with relations of higher arity, (P2) is a condition which is closely related to the basic linear programming relaxation of the instance, and (P3) is a condition which is closely related to the basic semidefinite relaxation of the instance. Barto and Kozik have raised the question of whether any instance of a bounded-width CSP which satisfies just (P1) and (P3) has a solution - this is a weaker consistency notion than all other consistency notions which are known to guarantee solvability. In this talk, I'll introduce an even weaker type of consistency than (P1) and (P3), and explain how we can use algebraic results about finite affine-free idempotent Taylor algebras in a purely black-box way to prove that this weaker consistency is strong enough to guarantee the existence of a solution. The algebraic input needed is a new type of subalgebra which I call a ``stable subalgebra'', which satisfies some amazingly strong axiomatic rules.
Stable subalgebras and weaker consistency for bounded width CSPs
Apr. 22, 2021 1pm (Zoom (vir…
Rep Theory
Fei Qi (University of Manitoba)
X
Meromorphic open-string vertex algebras (abbre. MOSVAs) is a noncommutative generalization of the usual vertex algebra defined by Yi-Zhi Huang in 2012. Vertex operators still satisfy the associativity but do not necessarily satisfy commutativity. In this talk I will illustrate nontrivial examples of MOSVAs and modules we know so far, including the universal bosonic construction, the universal fermionic construction, and the example from the geometry over constant curvature manifolds.