DIMACS Discrete Math/Theory of Computing Seminar


Title:

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

Speaker:

Armin Haken
DIMACS

Place:

Hill Center, Room 705 - NOTE ROOM CHANGE
Rutgers University

Time:

4:30 PM
Tuesday, October 29, 1996
Abstract:

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