Where graph theory meets uni...

2013-05-23 00:00 stxy View:[]

Speaker:Prof. Ralph McKenzie (Vanderbilt University)

Title:Where graph theory meets universal algebra: constraint satisfaction problems

Time:24, May, 15:00--16:00

Venue:Room 422 of School of Mathematics and Statistics

Abstract:It is conjectured that every constraint satisfaction problem is either tractable (i.e., has a deterministic polynomial time algorithm) or is NP-complete. It turns out that universal algebra has much to contribute toward resolving this conjecture. We survey the landscape.



Ph.D., University of Colorado, 1966

Professional Positions:

Professor, UC Berkeley, 1978–1994

Professor Emeritus, UC Berkeley, 1994–

Distinguished Professor, Vanderbilt University, 1994–

Awards and Honors:

Fulbright Senior Scholar, [Fall] 1989

Sloan Foundation Fellow, 1973–75

Last:Short Course on Computation... Next:The 1st Chongqing Workshop ...


College of Mathematics and Statistics
(C)Copyright: College of Mathematics and Statistics All rights reserved
Address:B1 building, Huxi campus of ChongQing University. Zip Code:401331