Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > STANISLAV ZIVNY:
All reports by Author Stanislav Zivny:

TR20-004 | 17th January 2020
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>




ISSN 1433-8092 | Imprint