Uniform Circuits for Arithmetic, Including Division

Dr. David Mix Barrington

University of Massachusetts, Amherst

April 15, 2004

12:40 - 1:40pm

Bailey Hall 312

Abstract

Real computers solve arithmetic problems in the end by performing a huge number of boolean operations on boolean values. Circuit complexity studies the size and depth of circuits that solve important problems. In this talk we will:

- Look at circuits that compute the basic binary arithmetic operations, addition and multiplication
- Explain the notion of circuit uniformity, with a precise theorem relating polynomial-size circuits to polynomial-time Turing machines, and
- Motivate and outline a presentation of uniform threshold circuits computing integer division using Chinese remaindering (recent joint work with Hesse and Allender)

Lunch will be provided at 12:00 in Steinmetz 237, and a discussion session for students will follow the talk, also in Steinmetz 237.