Dichotomy Theorems for Counting Problems II

Wednesday, January 27th, 2016, 1:30 pm–2:30 pm

Add to Calendar

Event:

Counting Complexity and Phase Transitions Boot Camp

Speaker:

Xi Chen (Columbia University)

Location:

Calvin Lab Auditorium

Constraint Satisfaction Problems (CSPs) have been studied extensively in the literature, and their counting version provides a sufficiently broad framework to address a large class of counting problems for which one can hope to prove complexity dichotomy theorems. In this talk we will review the recent sequence of dichotomy theorems on counting CSP and showcase some of the techniques developed in these works.

Complexity of generalized satisfiability counting problems, Creignou and Hermann

http://www.sciencedirect.com/science/article/pii/S0890540196900164

The complexity of the counting constraint satisfaction problem, Bulatov

http://dl.acm.org/citation.cfm?doid=2528384.2528400

An effective dichotomy for the counting constraint satisfaction problem, Dyer and Richerby

http://epubs.siam.org/doi/abs/10.1137/100811258

The complexity of weighted and unweighted #CSP, Bulatov, Dyer, Goldberg, Jalsenius, Jerrum and Richerby

http://www.sciencedirect.com/science/article/pii/S0022000011001474

Non-negative weighted #CSPs: An effective complexity dichotomy, Cai, Chen and Lu

http://arxiv.org/abs/1012.5659

Complexity of counting CSP with complex weights, Cai and Chen

http://arxiv.org/abs/1111.2384

The f irst session of this mini course will take place on Tuesday, January 26 from 11:00 am – 12:00 pm.

Download Video [2.0GB .mp4]

Attachment	Size
Dichotomy Theorems for Counting Problems II	305.02 KB