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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/ITA_2001__35_3_259_0/