[Colloquium] Talk by Amir Yehudayoff, IAS on December 1, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, December 1, 2009
Time: 3:00 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Amir Yehudayoff

From:		Institute for Advanced Study

Web page:	http://www.math.ias.edu/~amiry/

Title: Algebraic complexity with less relations (joint work with P.  
Hrubes and A. Wigderson).

Abstract: In his seminal paper, Valiant defined algebraic analogs for  
the complexity classes P and NP, which are called today VP and VNP,  
and showed that the permanent is complete for VNP. In this talk we  
study a more restricted algebraic world, a world in which the  
variables do not commute and associate. We show that, although  
restricted, this world exhibits some interesting properties: the  
permanent is complete even in the non-associative non-commutative  
version of VNP. We are also able to prove lower bounds for circuits in  
such a restricted world, and thus able to separate VP from VNP in a  
non-associative world.

The reception will be held prior to the talk in RY 255 at 2:30.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20091118/c922ef2a/attachment.htm