Caltech Home > PMA Home > Calendar > Reading Seminar
open search form
Monday, January 25, 2016
4:30 PM - 5:30 PM

Reading Seminar

Ehrenfeuct-Fraisse Games
Jalex Stark, Student, Caltech,

We willl study further the concept of L-definability for a fixed logic L, defined in the last lecture. We will use the method of Ehrenfeuct-Fraisse games to prove lower bounds for particular graph properties, e.g. that connectivity is not definable in first-order logic. Using these lower bounds, we will show that conjectures about logics capturing classes have important consequences in complexity theory.

For more information, please contact Martino Lupini by email at lupini@caltech.edu.