Fall 2016

Fellows Logic Open Seminar

Nov 28, 2016 2:00 pm – 3: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.