Settings

Theme

Simplified proof of the Constraint Satisfaction Problem Dichotomy Conjecture

arxiv.org

1 points by cevi 2 years ago · 1 comment

Reader

ceviOP 2 years ago

In 2017, Andrei Bulatov and Dmitriy Zhuk independently proved that every CSP template defines a problem which is either NP-complete or can be solved in polynomial time (they shared best paper at FOCS for this). However, the number of people who actually understand either of their proofs is still tiny, and no one has managed reduce the (enormous) running times of their algorithms. Zhuk just put out a much simpler argument with a cleaner abstraction of the crucial algebraic properties which are used in his proof.

By the way, if anyone is interested in a slightly more comprehensive exposition of the background material, I have been working for several years on writing up notes on the topic: https://raw.githubusercontent.com/notzeb/all/master/csp-note...

Keyboard Shortcuts

j
Next item
k
Previous item
o / Enter
Open selected item
?
Show this help
Esc
Close modal / clear selection