UMassCS Logo

Theory Seminar

David Mix Barrington
UMass Amherst Theory Group

Tuesday, February 21, 2012
4:00pm - 5:00pm
Computer Science Building, Room 140

"Arithmetic Circuit Classes: A Survey"

Circuit complexity normally measures the resources needed to solve problems with Boolean circuits, where the wires carry 0 or 1 values and the gates compute functions like AND, OR, and NOT. Size and depth constraints on families of these circuits give us complexity classes like AC^0, NC^1, NC, and P. In arithmetic circuits, the wires carry values from some number domain such as the naturals, the integers, or the reals, and the gates perform ariithmetic operations like addition and multiplication. We will survey some results on arithmetic circuit classes over the naturals and integers, such as #AC^0 and #NC^1. These are closely related to the counting classes that Marco discussed last week, such as #L and GapL.