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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.