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.  Zbl0956.68060
  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.  Zbl0719.68023
  4. P. Beame, S. Cook and H. Hoover, Log depth circuits for division and related problems. SIAM J. Comput.15 (1986) 994-1003.  Zbl0619.68047
  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.  Zbl0695.68053
  6. A. Borodin, On relating time and space to size and depth. SIAM J. Comput.6 (1977) 733-744.  Zbl0366.68039
  7. S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control64 (1985) 2-22.  Zbl0575.68045
  8. G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput.20 (1991) 756-765.  Zbl0736.68040
  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.  Zbl1053.68501
  11. N. Immerman, Descriptive Complexity. Springer-Verlag (1999).  
  12. D. Knuth, The Art of Computer Programming, Vol. 2. Addison-Wesley (1969).  Zbl0191.18001
  13. C. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci.71 (1990) 95-132.  Zbl0699.68069
  14. B. Litow, Computing context-free grammar generating series. Inform. and Comput. (in press).  Zbl1007.68085
  15. I. Macarie, Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput.27 (1998) 448-465.  Zbl0907.68081
  16. J. Reif, Logarithmic depth circuits for algebraic functions. SIAM J. Comput.15 (1986) 231-242.  Zbl0611.68014
  17. W. Ruzzo, On uniform circuit complexity. J. Comput. System Sci.22 (1981) 365-383.  Zbl0462.68013
  18. R. Tanaka and N. Szabo, Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968).  Zbl0168.15303
  19. H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag (1999).  Zbl0931.68055
  20. I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987).  Zbl0623.94018

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.