Calvin Lab Auditorium
Pebble games (based on Ehrenfeucht-Fraïssé games) are an important tool for analyzing the expressive power of logics. They are also related to efficient algorithms for approximating homomorphism and isomorphism on finite structures. In this short talk, I look at some questions arising from composing strategies in pebble games and some
algorithmic consequences that may follow.