Speaker: Martin Ziegler

Title: Algebraic Complexity Theory and Quantum Logic

Abstract:

Algebraic models of computation (like register machines) make one operation per step regardless of the value processed. They underly algorithms for sorting or in computational geometry. As opposed to bit models, algebraic methods permit to establish non-trivial lower bounds:
    We recall Morgenstern's elegant proof that the fast fourier transform is optimal; then proceed to the structural complexity theory and prove the quantum satisfiability problem complete for NP_R^0: a well-known discrete complexity class between NP and PSPACE. (Joint work with Christian Herrmann.)