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