YoVDO

A Deterministic Algorithm for Counting Colorings with 2Δ Colors

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Combinatorics Courses Algorithms Courses Computational Complexity Courses Partition Functions Courses Phase Transitions Courses

Course Description

Overview

Explore a deterministic algorithm for counting colorings with 2Δ colors in this 22-minute IEEE conference talk. Delve into the intricacies of Q-Coloring, randomized algorithms, and phase transitions. Examine concepts such as partition functions, dominos interpolation, and zero-free regions. Gain insights into triangle-free regions, entropy conditions, and the main ideas behind this innovative approach. Learn from speakers Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava as they present their findings and recap the key points of this advanced mathematical topic.

Syllabus

Introduction
QColoring
Results
Randomized Algorithm
What is Phase Transition
Partition Function
Dominos Interpolation
Zero Free Region
Triangle Free Region
Different Algorithm
Main Idea
Entropy Condition
Recap


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

Automata Theory
Stanford University via edX
Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX
算法设计与分析 Design and Analysis of Algorithms
Peking University via Coursera
How to Win Coding Competitions: Secrets of Champions
ITMO University via edX
Introdução à Ciência da Computação com Python Parte 2
Universidade de São Paulo via Coursera