DIMACS Discrete Math/Theory of Computing Seminar


An Exponential Lower Bound for Monotone Arithmetic Circuits and Prospects for Non-Monotone Lower Bounds


Armin Haken


Hill Center, Room 705 - NOTE ROOM CHANGE
Rutgers University


4:30 PM
Tuesday, October 29, 1996

An arithemetic circuit is analogous to a Boolean circuit, but the truth values can be arbitrary integers or real numbers. The talk will explain the exponential lower bound on monotone arithmetic circuits, that was obtained by Cook and myself. The power of monotone arithmetic circuits on slice functions shows that the methods used in this proof don't suffice for non-monotone Boolean circuit lower bounds. I will mention where I feel the hope for such bounds lies.

Document last modified on October 22, 1996