Division in logspace-uniform NC1

Andrew Chiu; George Davida; Bruce Litow

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 35, Issue: 3, page 259-275
  • ISSN: 0988-3754

Abstract

top
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., NC1 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 NC1.

How to cite

top

Chiu, Andrew, Davida, George, and Litow, Bruce. "Division in logspace-uniform NC1." RAIRO - Theoretical Informatics and Applications 35.3 (2010): 259-275. <http://eudml.org/doc/222086>.

@article{Chiu2010,
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., NC1 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 NC1. },
author = {Chiu, Andrew, Davida, George, Litow, Bruce},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Parallel complexity; NC; integer division; uniformity.; polynomial size circuit family},
language = {eng},
month = {3},
number = {3},
pages = {259-275},
publisher = {EDP Sciences},
title = {Division in logspace-uniform NC1},
url = {http://eudml.org/doc/222086},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Chiu, Andrew
AU - Davida, George
AU - Litow, Bruce
TI - Division in logspace-uniform NC1
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 3
SP - 259
EP - 275
AB - 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., NC1 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 NC1.
LA - eng
KW - Parallel complexity; NC; integer division; uniformity.; polynomial size circuit family
UR - http://eudml.org/doc/222086
ER -

References

top
  1. E. Allender, M. Agrawal and S. Datta, On TC0, AC0, and arithmetic circuits. J. Comput. System Sci.60 (2000) 395-421.  
  2. E. Allender and D.A. Mix Barrington, Uniform circuits for division: Consequences and problems (2000) , .  
  3. D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC1. J. Comput. System Sci.41 (1990) 274-306.  
  4. P. Beame, S. Cook and H. Hoover, Log depth circuits for division and related problems. SIAM J. Comput.15 (1986) 994-1003.  
  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.  
  6. A. Borodin, On relating time and space to size and depth. SIAM J. Comput.6 (1977) 733-744.  
  7. S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control64 (1985) 2-22.  
  8. G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput.20 (1991) 756-765.  
  9. W. Hesse, Division is in uniform TC0. Comp. Sci., U. Mass. Amherst (2000).  
  10. M.A. Hitz and E. Kaltofen, Integer division in residue number systems. IEEE Trans. Comput.44 (1995) 983-989.  
  11. N. Immerman, Descriptive Complexity. Springer-Verlag (1999).  
  12. D. Knuth, The Art of Computer Programming, Vol. 2. Addison-Wesley (1969).  
  13. C. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci.71 (1990) 95-132.  
  14. B. Litow, Computing context-free grammar generating series. Inform. and Comput. (in press).  
  15. I. Macarie, Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput.27 (1998) 448-465.  
  16. J. Reif, Logarithmic depth circuits for algebraic functions. SIAM J. Comput.15 (1986) 231-242.  
  17. W. Ruzzo, On uniform circuit complexity. J. Comput. System Sci.22 (1981) 365-383.  
  18. R. Tanaka and N. Szabo, Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968).  
  19. H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag (1999).  
  20. I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987).  

NotesEmbed ?

top

You must be logged in to post comments.