Fall 2016

Fellows Logic Open Seminar

Monday, November 28th, 2016, 2:00 pm3:30 pm

Add to Calendar


Calvin Lab Rm 116

Equivalence in K-Variable Logics

This talk focuses on equivalence in finite variable logics, that is, whether two finite structures satisfy the same k-variable first-order sentences. I present an old open problem on the complexity of testing equivalence and discuss techniques to prove lower bounds via the corresponding k-pebble game.