# 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.

dimacs-www@dimacs.rutgers.edu
Document last modified on October 22, 1996