Speaker: Robert McGrail

Title: P/NP Dichotomy for Finite Quandles

Date/Time:  Thursday, 22 March @ 13:40 pm

Place: FENS - L055

You are cordially invited to attend the colloquium given by Robert McGrail (Bard College, NY) on Thursday, 22 March 2018, in FENS-L055 at 1.40 pm. 

Abstract:  In the 1990's, Jeavons showed that every finite algebra corresponds to a class of constraint satisfaction problems.  Vardi later conjectured that idempotent algebras exhibit P/NP dichotomy:  Every non NP-complete algebra in this class must be tractable.  The speaker demonstrates that dichotomy in finite quandles follows from a very strong notion of connectivity in Cayley graphs.  Moreover, P/NP membership is first-order axiomatizable in an important subclass of quandles.

Contact: Yasemin Şengül Tezel