Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-034 | 3rd September 1997 00:00

#### Counting in uniform \$TC^0\$

TR97-034
Authors: Jui-Lin Lee
Publication: 10th September 1997 21:25
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