YoVDO

Twin-width I - Tractable FO Model Checking

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Logic Courses Dynamic programming Courses Formal Methods Courses

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 Nature
IEEE 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