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:

  1. Look at circuits that compute the basic binary arithmetic operations, addition and multiplication
  2. Explain the notion of circuit uniformity, with a precise theorem relating polynomial-size circuits to polynomial-time Turing machines, and
  3. 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.