The Hardness of the Functional Orientation 2-Color Problem

Søren Bøg, Morten Stöckel, Hjalte Wedel Vildhøj

We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput., 37(5), 2008]. For this deci…