A Dichotomy Theorem for Nonuniform CSPs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Oct 2017Embargo end date: 01 Mar 2017Publisher:IEEEJournal:2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)

Authors: Andrei A. Bulatov;

doi: 10.1109/focs.2017.37 , 10.48550/arxiv.1703.03021

arXiv: 1703.03021

A Dichotomy Theorem for Nonuniform CSPs

- Summary
- Subjects
- Metrics

Abstract

Apart from correcting typos and inaccuracies, this version of the paper is different from the first arXiv version in the following ways: A self-contained high level presentation of the main results is added; the Preliminaries section is extended, several proofs are reorganized and expanded for improved readability

In this paper we prove the Dichotomy Conjecture on the complexity of nonuniform constraint satisfaction problems posed by Feder and Vardi.

Related Organizations

Simon Fraser University
Canada

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	142
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 1%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 1%