## Contact Info

Pure MathematicsUniversity of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x33484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

Monday, April 28, 2014 — 3:30 PM EDT

The quantified constraint satisfaction problem (QCSP) is the computational problem of deciding, given a structure and a first-order prenex sentence whose quantifier-free part is the conjunction of atoms, whether or not the sentence holds on the structure. One obtains a family of problems by defining, for each structure B, the problem QCSP(B) to be the QCSP where the structure is fixed to be B. We will discuss the research program of trying to classify the complexity of QCSP(B) for each finite structure B. It is possible to associate an algebra to each finite structure in such a way that studying the algebra of a structure gives insight into the QCSP complexity of the structure. We will overview the use of universal-algebraic notions and techniques in this research program. In particular, there is a close connection between QCSP complexity and the growth rate of the number of elements needed to generate the powers A1,A2, ... of an algebra A: showing an at-most polynomial growth rate can (essentially) be translated to a complexity upper bound for a structure with algebra A. This research area gives (we believe) a fascinating interplay between computational complexity, universal algebra, and logic.

This talk will partially be based on the overview article available at Meditations on Quantified Constraint Satisfaction.

Special presentation.

Location

MC - Mathematics & Computer Building

4206

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

University of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x33484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1