Holographic Algorithms and Complexity Dichotomy Theorems

Jin-Yi Cai
Professor
Computer Sciences Department, University of Wisconsin - Madison
Location: 
TECH Center 111
Date: 
Wednesday, September 25, 2013 - 11:30
Complexity Theory is the study of intrinsic difficulties of computational problems. The famous conjecture that P is not equal to NP essentially states that it is intrinsically harder to find proofs than to verify them.  It has a fundamental importance in many areas of computer science, from computer security to our basic understanding of the nature of efficient computation.
 
Holographic algorithms can solve a number of problems in polynomial time which would seem to require exponential time. They challenge our conception of what polynomial time computations can do, in view of the P vs. NP question.
 
Complexity dichotomy theorems are classification theorems of a broad class of problems. We aim to classify every problem within the class to be either solvable in polynomial time, or intractable.There have been significant progress in achieving dichotomy theorems for counting problems. 
 
In this talk I will discuss some recent developments, including the frameworks of (1) Graph  homomorphisms, (2) Constraint Satisfaction Problems, and (3) Holant Problems.No specialized background is assumed.