Division in logspace-uniform NC 1
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 259-275.

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 .

Classification : 68Q05, 68Q10, 68Q15, 68Q17
Mots-clés : parallel complexity, NC, integer division, uniformity 
@article{ITA_2001__35_3_259_0,
     author = {Chiu, Andrew and Davida, George and Litow, Bruce},
     title = {Division in logspace-uniform $\mbox{NC}^1$},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {259--275},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {3},
     year = {2001},
     mrnumber = {1869217},
     zbl = {1014.68062},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_3_259_0/}
}
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
SP  - 259
EP  - 275
VL  - 35
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_3_259_0/
LA  - en
ID  - ITA_2001__35_3_259_0
ER  - 
%0 Journal Article
%A Chiu, Andrew
%A Davida, George
%A Litow, Bruce
%T Division in logspace-uniform $\mbox{NC}^1$
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 259-275
%V 35
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_3_259_0/
%G en
%F ITA_2001__35_3_259_0
Chiu, Andrew; Davida, George; Litow, Bruce. Division in logspace-uniform $\mbox{NC}^1$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 259-275. http://archive.numdam.org/item/ITA_2001__35_3_259_0/

[1] E. Allender, M. Agrawal and S. Datta, On TC 0 , AC 0 , and arithmetic circuits. J. Comput. System Sci. 60 (2000) 395-421. | MR | Zbl

[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] D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC 1 . J. Comput. System Sci. 41 (1990) 274-306. | MR | Zbl

[4] P. Beame, S. Cook and H. Hoover, Log depth circuits for division and related problems. SIAM J. Comput. 15 (1986) 994-1003. | MR | Zbl

[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. | MR | Zbl

[6] A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6 (1977) 733-744. | MR | Zbl

[7] S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control 64 (1985) 2-22. | MR | Zbl

[8] G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. | MR | Zbl

[9] W. Hesse, Division is in uniform TC 0 . Comp. Sci., U. Mass. Amherst (2000). | MR

[10] M.A. Hitz and E. Kaltofen, Integer division in residue number systems. IEEE Trans. Comput. 44 (1995) 983-989. | MR | Zbl

[11] N. Immerman, Descriptive Complexity. Springer-Verlag (1999). | MR | Zbl

[12] D. Knuth, The Art of Computer Programming, Vol. 2. Addison-Wesley (1969). | MR | Zbl

[13] C. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71 (1990) 95-132. | MR | Zbl

[14] B. Litow, Computing context-free grammar generating series. Inform. and Comput. (in press). | Zbl

[15] I. Macarie, Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput. 27 (1998) 448-465. | MR | Zbl

[16] J. Reif, Logarithmic depth circuits for algebraic functions. SIAM J. Comput. 15 (1986) 231-242. | MR | Zbl

[17] W. Ruzzo, On uniform circuit complexity. J. Comput. System Sci. 22 (1981) 365-383. | MR | Zbl

[18] R. Tanaka and N. Szabo, Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968). | Zbl

[19] H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag (1999). | MR | Zbl

[20] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). | MR | Zbl