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.
Brief：
Education:
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
