Division in logspace-uniform NC¹
Chiu, Andrew, Davida, George, and Litow, Bruce (2001) Division in logspace-uniform NC¹. RAIRO - Theoretical Informatics and Applications, 35 (3). pp. 259-275.
![[img]](https://researchonline.jcu.edu.au/style/images/fileicons/application_pdf.png) |
PDF (Published Version)
- Published Version
Restricted to Repository staff only |
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., NC¹ 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¹.
| Item ID: | 491 |
|---|---|
| Item Type: | Article (Research - C1) |
| ISSN: | 1290-385X |
| Keywords: | parallel complexity, NC, integer division, uniformity |
| Additional Information: | Copyright EDP Sciences 2001 Reproduced with permission from EDP Sciences. RAIRO - Theoretical Informatics and Applications: http://www.rairo-ita.org |
| Date Deposited: | 03 Nov 2006 |
| FoR Codes: | 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 0% |
| Downloads: |
Total: 1 |
| More Statistics |
Actions (Repository Staff Only)
 |
Item Control Page |