Twin-width I - Tractable FO Model Checking
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 24-minute IEEE conference talk on twin-width and its applications in tractable first-order model checking. Delve into concepts such as trigraphs, contraction sequences, unit intervals, and ktman graphs. Learn about Hamiltonian paths, bounded twin-width graph formula checking, and interpretations. Discover the role of magnetic stability in FO model checking and understand the dynamic programming approach used in this context. Gain insights from authors Idouard Bonnet, Eun Jung Kim, Stiphan Thomassi, and Rimi Watrigant from LIP, ENS Lyon, and LAMSADE, Paris-Dauphine University.
Syllabus
Introduction
Trigraphs
contraction sequence
something more
unit interval
ktman graphs
Hamiltonian path
Bounded Twin
Graph Formula Checking
Interpretations
Magnetic stability
FO model checking
Dynamic programming
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube