Injective hardness condition for PCSPs
<|reference_start|>Injective hardness condition for PCSPs: We present a template for the Promise Constraint Satisfaction Problem (PCSP) which is NP-hard but does not satisfy the current state-of-the-art hardness condition [ACMTCT'21]. We introduce a new "injective" condition based on the smooth version of the layered PCP Theorem and use this new condition to confirm that the problem is indeed NP-hard. In the second part of the article, we establish a dichotomy for Boolean PCSPs defined by templates with polymorphisms in the set of linear threshold functions. The reasoning relies on the new injective condition.<|reference_end|>
@article{banakh2024injective,
    title={Injective hardness condition for PCSPs},
    author={Demian Banakh and Marcin Kozik},
    journal={arXiv preprint arXiv:2405.10774},
    year={2024},
    doi={10.1145/3661814.3662072},
    archivePrefix={arXiv},
    eprint={2405.10774},
    primaryClass={cs.CC}
}