Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

IEEE via YouTube

Overview

Explore a comprehensive analysis of graph homomorphisms with complex values on bounded degree graphs in this 25-minute IEEE conference talk. Delve into the intricacies of partition functions, vertex weights, and the ease model as presented by Jin-Yi Cai and Artsiom Hovarau from the University of Wisconsin-Madison. Examine the complex theory behind dichotomy and generating sets, and understand the purification structure and thickening edge gadgets. Investigate the multiplicatively broken one matrix and non-multiplicative block requirements through the Vandermonde argument. Learn about the contrapositive case gadgets, vendor mode, and exponential polynomial transfer procedure. Follow the outline of the main proof, including meta arguments and constructivity, to gain a deeper understanding of this advanced topic in graph theory and computational complexity.

Syllabus

Introduction
Graph homomorphism
Partition function
Vertex weights
Partition functions
Ease model
Other similar models
Complex theory
Dichotomy
Generating Sets
Purification
Structure
Thickening
Edge Gadgets
Multiplicatively Broken One
Matrix
Nonmultiplicative Block Requirements
Vandermot Argument
Contrapositive
Case gadgets
Replace every vertex
Vendor mode
Exponential polynomial
Transfer procedure
Outline main proof
Example of meta argument
Strengthens
Constructivity

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.