Arithmetic Circuit Classes: A Survey

21 Feb
02/21/2012 -
11:00am to 12:00pm
Theory Seminar

David Mix Barrington
UMass Amherst Theory Group

Computer Science Building, Room 140

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.