Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-034 | 3rd September 1997 00:00

Counting in uniform $TC^0$

RSS-Feed




TR97-034
Authors: Jui-Lin Lee
Publication: 10th September 1997 21:25
Downloads: 3531
Keywords: 


Abstract:

In this paper we first give a uniform $AC^0$ algorithm which uses
partial sums to compute multiple addition. Then we use it to show
that multiple addition is computable in uniform $TC^0$ by using
$count$ only once sequentially. By constructing bit matrix for
multiple addition, we prove that multiple product with
poly-logarithmic size is computable in uniform $TC^0$
(by using $count$ $k+1$ times sequentially when the product
has size $O((\log n)^k)$). We also prove that multiple product
with sharply bounded size is computable in uniform $AC^0$.



ISSN 1433-8092 | Imprint