Citation
A. Chiu et al., Division in logspace-uniform NC, RAIRO-INF, 35(3), 2001, pp. 259-275
Citations number
20
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
ISSN journal
09883754
→ ACNP
Volume
35
Issue
3
Year of publication
2001
Pages
259 - 275
Database
ISI
SICI code
0988-3754(200105/06)35:3<259:DILN>2.0.ZU;2-F
Abstract
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial si
ze circuit family for integer division. However, the family was not logspac
e-uniform. In this paper we describe log-depth, polynomial size, logspace-u
niform, i.e., NC1 circuit family for integer division. In particular, by a
well-known result this shows that division is in logspace. We also refine t
he method of the paper to show that division is in dlogtime-uniform NC1.