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