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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.