C01 Postdoc Welcome Seminar

This is a seminar for introducing Chirstian who came to Tokyo
as a C01 postdoc fellow.  Please join us for this seminar.
Let me know if anyone wants to join the seminar by polycom.

Osamu Watanabe
=====
speaker: Dr. Cristian Engels
date: Nov. 12 (Thur.) 13:30 - 15:30
place: ELC seminar room

title: Two Theorems on Arithmetic Circuit Complexity
abstract:
In this presentation we give a short introduction to the field
of arithmetic  circuit complexity as well as show two theorems
as examples on the kind of problems one can look at.

The first problem is based on graph homomorphisms and asks how
hard  polynomials based on enumerating all homomorphisms from
some fixed graph class G to a given graph H are. We show major
dichotomies for many natural graph classes.

The second theorem looks at non-commutative permanent/determinant.
We show  here that for even very restricted graph classes the
non-commutative permanent/determinant on these graphs need large 
arithmetic  branching programs. Arithmetic branching programs here
are a specialized arithmetic circuit class.

host: watanabe@is.titech.ac.jp