CS 880: 2012 Complexity of Counting Problems

Time: 9:30 am -- 10:45 am. T Th.
Room CS 1289

Professor: Jin-Yi Cai
Computer Sciences Department
Office Room CS 4393
University of Wisconsin - Madison
1210 West Dayton Street
Madison, WI 53706
U.S.A.
PHONE: (608) 262-3158
EMAIL: jyc AT cs DOT wisc DOT edu
Dept Web Page

Lecture Notes

Jan 24 pdf
Jan 26 pdf
Jan 31 pdf
Feb 2 pdf
Feb 7 pdf
Feb 9 pdf
Feb 14 pdf
Feb 16 pdf
Feb 21 pdf
Feb 23 pdf
Feb 28 pdf
March 1 pdf
March 6 pdf
March 8 pdf
March 13 pdf
March 15 pdf
March 20 pdf
March 22 pdf
March 27 pdf
March 29 pdf
April 3, 5 spring break
April 10 pdf
April 12 pdf
April 17 pdf
April 19 pdf
April 24 pdf
April 26 pdf
May 1 pdf
May 3 pdf
May 8 pdf
May 10 pdf

Papers on matchgates and holographic algorithms :

A Survey on Holographic Algorithms pdf
(Pinyan Lu) Complexity Dichotomies of Counting Problems (a survey)
(Valiant) Holographic Algorithms pdf
(Valiant) Accidental Algorithms pdf
Valiant's Holant Theorem and Matchgate Tensors pdf
On the Theory of Matchgate Computations ps pdf
Some Results on Matchgates and Holographic Algorithms ps pdf
On Symmetric Signatures in Holographic Algorithms ps pdf
Holographic Algorithms: From Art to Science pdf
Bases Collapse in Holographic Algorithms pdf
On Block-wise Symmetric Signatures for Matchgates ps pdf
Holographic Algorithms: The Power of Dimensionality Resolved pdf
Signature Theory in Holographic Algorithms pdf

Papers on Holant problems:

Holographic Algorithms by Fibonacci Gates pdf
Holographic Reduction, Interpolation and Hardness pdf
Computational Complexity of Holant Problems pdf
A computational proof of complexity of some restricted counting problems pdf
Holant Problems for Regular Graphs with Complex Edge Functions pdf
Michael Kowalczyk's PhD thesis pdf
From Holant To #CSP And Back: Dichotomy For Holant^c Problems pdf
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP pdf
Dichotomy for Holant^* Problems of Boolean Domain pdf

Papers on CSP:

(Andrei Bulatov and Victor Dalmau) Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem pdf
The Complexity of Complex Weighted Boolean #CSP pdf
(Andrei Bulatov) The Complexity of the Counting Constraint Satisfaction Problem pdf
(Martin Dyer, David Richerby) An Effective Dichotomy for the Counting Constraint Satisfaction Problem pdf
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy pdf
Complexity of Counting CSP with Complex Weights pdf

Papers on Graph Homomorphisms:

(Martin Dyer and Catherine Greenhill) The complexity of counting graph homomorphisms pdf corrigendum
(Andrei Bulatov and Martin Grohe) The Complexity of Partition Functions pdf
(L.A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley.) A complexity dichotomy for partition functions with mixed signs pdf
(Martin Dyer, Leslie Ann Goldberg and Mike Paterson) On Counting Homomorphisms to Directed Acyclic Graphs pdf
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights pdf
(Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley) A Complexity Dichotomy for Partition Functions with Mixed Signs pdf
Graph Homomorphisms with Complex Values: A Dichotomy Theorem paper in pdf
(My talk based on this paper at Brown ICERM workshop)

Here is an article from American Scientist Magazine on Holographic Algorithms by Brian Hayes. (Go to American Scientist web site)

Here are some talks given on related topics

Talk at ICALP 06 on Matchgate Computations. pdf

Talk at STACS 07 on Symmetric Signatures. pdf

Talk at MIT and Brown 2008 on Holographic Algorithms. pdf

Talk at Univ. of Chicago on Complexity Dichotomy of Graph Homomorphisms. pdf

Talk at Les Valiant Celebration (STOC 2009) pdf

Talk at Asian Association for Algorithms and Computation (AAAC). pdf

Talk at Dagstuhl pdf