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] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1051/ita:2001119

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 (Refereed Research - C1)
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

ISSN: 1290-385X
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 Item Control Page