You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Leeds » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Leeds

Return to search Previous output Next output

Output 15 of 95 in the submission

Article title

An Effective Dichotomy for the Counting Constraint Satisfaction Problem

Type

D - Journal article

DOI

10.1137/100811258

Title of journal

SIAM Journal on Computing

Article number

Volume number

Issue number

First page of article

1245

ISSN of journal

0097-5397

Year of publication

2013

URL

Number of additional authors

Additional information

<10>This paper proves a decidable complexity dichotomy for counting constraint satisfaction problems. Bulatov (2008) had given a much more complicated proof, without decidability. This paper gives an elementary proof of a new criterion for the dichotomy, and shows its decidability. An earlier conference version appeared in STOC2010 (ACM Symposium on Theory of Computing, one of the best two in computer science theory), was selected for a special edition of SIAM Journal on Computing (one of the two best in computer science theory). The proof techniques have generated further results, including a generalisation by Cai and Chen (STOC2012) to complex-weighted problems.

Interdisciplinary

Cross-referral requested

Research group

None

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract