|
Rutgers University
DCIS PhD Defense
Date: Monday, December 8, 2003
Time: 3:00 P.M.
Location: CoRE Building room 301, Busch Campus, Rutgers University
Title: Bounded Depth Arithmetic Circuits
Speaker: Samir Datta, Rutgers University
Defense committee: Prof. Eric Allender, Prof. Endre Szemeredi, Prof. Michael
Saks, Prof. Pierre McKenzie
Abstract:
Continuing a line of investigation that
has studied the function classes  ,  ,  , and  , we study the class of functions  . One way o define  is as the class of functions
computed by constant-depth polynomial-size arithmetic circuits of unbounded
fan-in addition and multiplication gates. In contrast to the preceding
function classes, for which we know no nontrivial lower bounds, lower bounds
for  follow easily
from established circuit lower bounds.
One of our main results is a
characterization of  in terms of  : A language A is in  if and only if there is a  function f and a number k such that
Using the standard naming conventions in literature, this yields:
 .
Another restatement of this
characterization is that  can be simulated by constant
depth arithmetic circuits, with a single threshold gate. We hope that perhaps
this characterization of  in terms of  circuits might provide a new
avenue of attack for proving lower bounds.
Our characterization differs markedly
from earlier characterizations of  in terms of arithmetic
circuits over finite fields. Using our model of arithmetic circuits,
computation over finite fields yields .
We also resolve several questions
regarding the closure properties of  and  , and characterize  in terms of counting paths in
a specific family of bounded-width graphs.
All Are Welcome To
Attend
|
