Division in logspace-uniform NC 1

Andrew Chiu; George Davida; Bruce Litow

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 3, page 259-275
  • ISSN: 0988-3754

Abstract

top
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC 1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC 1 .

How to cite

top

Chiu, Andrew, Davida, George, and Litow, Bruce. "Division in logspace-uniform $\mbox{NC}^1$." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.3 (2001): 259-275. <http://eudml.org/doc/92665>.

@article{Chiu2001,
abstract = {Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., $\mbox\{NC\}^1$ circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform $\mbox\{NC\}^1$.},
author = {Chiu, Andrew, Davida, George, Litow, Bruce},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {parallel complexity; NC; integer division; uniformity; polynomial size circuit family},
language = {eng},
number = {3},
pages = {259-275},
publisher = {EDP-Sciences},
title = {Division in logspace-uniform $\mbox\{NC\}^1$},
url = {http://eudml.org/doc/92665},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Chiu, Andrew
AU - Davida, George
AU - Litow, Bruce
TI - Division in logspace-uniform $\mbox{NC}^1$
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 3
SP - 259
EP - 275
AB - Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., $\mbox{NC}^1$ circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform $\mbox{NC}^1$.
LA - eng
KW - parallel complexity; NC; integer division; uniformity; polynomial size circuit family
UR - http://eudml.org/doc/92665
ER -

References

top
  1. [1] E. Allender, M. Agrawal and S. Datta, On TC 0 , AC 0 , and arithmetic circuits. J. Comput. System Sci. 60 (2000) 395-421. Zbl0956.68060MR1784585
  2. [2] E. Allender and D.A. Mix Barrington, Uniform circuits for division: Consequences and problems (2000) allender@cs.rutgers.edu, barring@cs.umass.edu 
  3. [3] D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC 1 . J. Comput. System Sci. 41 (1990) 274-306. Zbl0719.68023MR1079468
  4. [4] P. Beame, S. Cook and H. Hoover, Log depth circuits for division and related problems. SIAM J. Comput. 15 (1986) 994-1003. Zbl0619.68047MR861365
  5. [5] A. Bertoni, M. Goldwurm and P. Massazza, Counting problems and algebraic formal power series in noncommuting variables. Inform. Process. Lett. 34 (1990) 117-121. Zbl0695.68053MR1059975
  6. [6] A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6 (1977) 733-744. Zbl0366.68039MR461984
  7. [7] S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control 64 (1985) 2-22. Zbl0575.68045MR837088
  8. [8] G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. Zbl0736.68040MR1105936
  9. [9] W. Hesse, Division is in uniform TC 0 . Comp. Sci., U. Mass. Amherst (2000). MR2065855
  10. [10] M.A. Hitz and E. Kaltofen, Integer division in residue number systems. IEEE Trans. Comput. 44 (1995) 983-989. Zbl1053.68501MR1349940
  11. [11] N. Immerman, Descriptive Complexity. Springer-Verlag (1999). Zbl0918.68031MR1732784
  12. [12] D. Knuth, The Art of Computer Programming, Vol. 2. Addison-Wesley (1969). Zbl0191.18001MR633878
  13. [13] C. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71 (1990) 95-132. Zbl0699.68069MR1050080
  14. [14] B. Litow, Computing context-free grammar generating series. Inform. and Comput. (in press). Zbl1007.68085
  15. [15] I. Macarie, Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput. 27 (1998) 448-465. Zbl0907.68081MR1616560
  16. [16] J. Reif, Logarithmic depth circuits for algebraic functions. SIAM J. Comput. 15 (1986) 231-242. Zbl0611.68014MR822202
  17. [17] W. Ruzzo, On uniform circuit complexity. J. Comput. System Sci. 22 (1981) 365-383. Zbl0462.68013MR633540
  18. [18] R. Tanaka and N. Szabo, Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968). Zbl0168.15303
  19. [19] H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag (1999). Zbl0931.68055MR1704235
  20. [20] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473

NotesEmbed ?

top

You must be logged in to post comments.