Since deciding whether a given graph is 3-colourable is NP-complete, and checking validity of a colouring is an easy problem, also the problem of finding a colouring of a 3-colourable graph with 3 colours is a well-known NP-complete. One might be interested in a relaxed version of this problem, e.g., finding a colouring of a 3-colourable graph that uses 6 colours. This falls into a more general scope of so-called promise constraint satisfaction problem (PCSP). We will describe the basics of a theory characterising when one promise constraint satisfaction problem can be reduced to another using a gadget reduction.
A theory of gadget reductions for promise constraint satisfaction I
Feb. 18, 2021 1pm (Zoom (vir…
Rep Theory
Bin Gui (Rutgers University)
X
Given a strongly rational unitary VOA , a Hermitian form on the space of its intertwining operators was introduced recently to understand the unitarity of the representation modular tensor category . It was actually shown that, along with some natural assumptions, if this Hermitian form (which is necessarily non-degenerate) is positive, namely, if it is an inner product, then is unitary. The crucial step of this story is to prove the positivity of the Hermitian form. In this talk, I give a geometric interpretation of this positivity problem using the idea (self)conjugate Riemann surfaces and (self)conjugate conformal blocks.
A theory of gadget reductions for promise constraint satisfaction I