On Boolean PCSPs with Polynomial Threshold Polymorphisms
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911185881792512 |
|---|---|
| author | Michno, Katzper |
| author_facet | Michno, Katzper |
| contents | In pursuit of a deeper understanding of Boolean Promise Constraint Satisfaction Problems (PCSPs), we identify a class of problems with restricted structural complexity, which could serve as a promising candidate for complete characterization. Specifically, we investigate the class of PCSPs whose polymorphisms are Polynomial Threshold Functions (PTFs) of bounded degree. We obtain two complexity characterization results: (1) with a hardness condition introduced in [ACMTCT'21], we establish a complete complexity dichotomy in the case where coefficients of PTF representations are non-negative; (2) dropping the non-negativity assumption, we show a hardness result for PTFs admitting coordinates with significant influence, conditioned on the Rich 2-to-1 Conjecture proposed in [ITCS'21]. In order to prove the latter, we show that a random 2-to-1 minor map retains significant coordinate influence over the $p$-biased hypercube with constant probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26248 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Boolean PCSPs with Polynomial Threshold Polymorphisms Michno, Katzper Computational Complexity In pursuit of a deeper understanding of Boolean Promise Constraint Satisfaction Problems (PCSPs), we identify a class of problems with restricted structural complexity, which could serve as a promising candidate for complete characterization. Specifically, we investigate the class of PCSPs whose polymorphisms are Polynomial Threshold Functions (PTFs) of bounded degree. We obtain two complexity characterization results: (1) with a hardness condition introduced in [ACMTCT'21], we establish a complete complexity dichotomy in the case where coefficients of PTF representations are non-negative; (2) dropping the non-negativity assumption, we show a hardness result for PTFs admitting coordinates with significant influence, conditioned on the Rich 2-to-1 Conjecture proposed in [ITCS'21]. In order to prove the latter, we show that a random 2-to-1 minor map retains significant coordinate influence over the $p$-biased hypercube with constant probability. |
| title | On Boolean PCSPs with Polynomial Threshold Polymorphisms |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2509.26248 |