Tree-Depth and the Formula Complexity of Subgraph Isomorphism
Offered By: IEEE via YouTube
Course Description
Overview
Explore the intricate relationship between tree-depth and formula complexity in subgraph isomorphism through this insightful 25-minute IEEE conference talk. Delve into problem definitions, special cases, and formula complexity as presented by Deepanshu Kush from the University of Toronto and Benjamin Rossman from Duke University. Examine conjectures surrounding tree width and tree depth, and investigate graph minor approximation and input distribution. Gain a deeper understanding of complexity measures and supplementary results while considering potential solutions and open problems in this fascinating area of graph theory and computational complexity.
Syllabus
Introduction
Problem Definition
Special Cases
Formula Complexity
conjectures
tree width and tree depth
results
digression
graph minor approximation
input distribution
Complexity measure
Supplementary results
Solution
Open Problems
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Aplicaciones de la teoría de grafos a la vida realMiríadax Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X] Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer