3 papers
quant-ph2025
Classical Simulation of Quantum CSP Strategies
Demian Banakh, Lorenzo Ciardo, Marcin Kozik +1
We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra…
cs.CC2025
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be…
cs.CC2024
Injective hardness condition for PCSPs
Demian Banakh, Marcin Kozik
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 i…