Fall 2014

Algebraic Complexity Seminar

Oct. 10, 2014 11:00 am12:00 pm

Add to Calendar


Neeraj Kayal (Microsoft Research India)


Calvin Lab 116

A Sample of Lower Bounds in Algebraic Complexity

We will see some lower bounds for restricted classes of arithmetic circuits, including monotone circuits and multilinear formulas. (Over the reals) a circuit is monotone if it only uses nonnegative real constants. A circuit is multilinear if the syntactic degree with respect to every variable is 1.