On the complexity of symmetric vs. functional PCSPs

The complexity of the promise constraint satisfaction problem \ (PCSP (A, B) \) is largely unknown, even for symmetric \ (A\) and \ (B\), except for the case when \ (A\) and \ (B\) are Boolean. First, we establish a dichotomy for \ (PCSP (A, B) \) where \ (A, B\) are symmetric, \ (B\) is functional (i. e. any \ (r-1\) elements of an \ (r\) -ary tuple uniquely determines the last one), and \ ( (A, B) \) satisfies technical conditions we introduce called dependency and additivity. This result implies a dichotomy for \ (PCSP (A, B) \) with \ (A, B\) symmetric and \ (B\) functional if (i) \ (A\) is Boolean, or (ii) \ (A\) is a hypergraph of a small uniformity, or (iii) \ (A\) has a relation \ (R^A\) of arity at least 3 such that the hypergraph diameter of \ ( (A, R^A) \) is at most 1. Second, we show that for \ (PCSP (A, B) \), where \ (A\) and \ (B\) contain a single relation, \ (A\) satisfies a technical condition called balancedness, and \ (B\) is arbitrary, the combined basic linear programming relaxation (\ (BLP\) ) and the affine integer programming relaxation (\ (AIP\) ) is no more powerful than the (in general strictly weaker) \ (AIP\) relaxation. Balanced \ (A\) include symmetric \ (A\) or, more generally, \ (A\) preserved by a transitive permutation group.