Relationships among PL, #L, and the determinant
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 1, pp. 1-21. 
@article{ITA_1996__30_1_1_0,
     author = {Allender, Eric and Ogihara, Mitsunori},
     title = {Relationships among $PL$, $\#L$, and the determinant},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {1--21},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {1},
     year = {1996},
     mrnumber = {1398856},
     zbl = {0851.68033},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1996__30_1_1_0/}
}
TY  - JOUR
AU  - Allender, Eric
AU  - Ogihara, Mitsunori
TI  - Relationships among $PL$, $\#L$, and the determinant
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 1
EP  - 21
VL  - 30
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_1_1_0/
LA  - en
ID  - ITA_1996__30_1_1_0
ER  - 
%0 Journal Article
%A Allender, Eric
%A Ogihara, Mitsunori
%T Relationships among $PL$, $\#L$, and the determinant
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 1-21
%V 30
%N 1
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1996__30_1_1_0/
%G en
%F ITA_1996__30_1_1_0
Allender, Eric; Ogihara, Mitsunori. Relationships among $PL$, $\#L$, and the determinant. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 1, pp. 1-21. http://www.numdam.org/item/ITA_1996__30_1_1_0/

1. E. Allender, Oracles vs Proof techniques that do not relativize, Proc. SIGAL International Symposium on Algorithms, Lecture Notes in Computer Science, 1990, 450, pp. 39-52. | MR

2. E. Allender, R. Beals and M. Ogihara, The complexity of matrix rank and feasible systems of linear equations, to appear in Proc. 28th STOC, 1996. | MR | Zbl

3. E. Allender and J. Jiao, Depth reduction for noncommutative arithmetic circuits, Proc. 25th STOC, 1993, pp. 515-522.

4. C. Àlvarez, J. Balcázar and B. Jenner, Adaptive logspace reducibility and parallel time, Mathematical Systems Theory, 1995, 28, pp. 117-140. | MR | Zbl

5. C. Àlvarez and B. Jenner, A very hard log-space counting class, Theoretical Computer Science, 1993, 107, pp. 3-30. | MR | Zbl

6. J. Balcázar, Adaptive logspace and depth-bounded reducibilities, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 240-254.

7. S. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 1984, 18, pp. 147-150. | MR | Zbl

8. A. Borodin, S. Cook and N. Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, 1983, 48, pp. 113-136. | MR | Zbl

9. A. Borodin, S. Cook, P. Dymond, W. Ruzzo and M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18, pp. 559-578. | MR | Zbl

10. S. Buss, S. Cook, A. Gupta and V. Ramachandran, An optimal parallel algorithm for formula evaluation, SIAM Journal on Computing, 1992, 21, pp. 755-780. | MR | Zbl

11. A. Ben-Dor and S. Halevi, Zero-one permanent is #P-complete, a simpler proof, Proc. 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93), IEEE press.

12. D. Barrington, N. Immerman and H. Straubing, On uniformity within NC1, Journal of Computer and System Sciences, 1990, 41, pp. 274-306. | MR | Zbl

13. R. Beigel, N. Reingold and D. Spielman, PP is closed under intersection, Journal of Computer and System Sciences, 1995, 50, pp. 191-202. | MR | Zbl

14. G. Buntrock, C. Damm, U. Hertrampf and C. Meinel, Structure and Importance of Logspace MOD-Classes, Mathematical Systems Theory, 1992, 25, pp. 223-237. | MR | Zbl

15. S. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, 1985, 64, pp. 2-22. | MR | Zbl

16. C. Damm, DET = L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991.

17. S. Fenner, L. Fortnow and S. Kurtz, Gap-definable counting classes, Journal of Computer and System Sciences, 1994, 48, pp. 116-148. | MR | Zbl

18. L. Fortnow and N. Reingold, PP is closed under truth-table reductions, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 13-15. | Zbl

19. J. Gill, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 1977, 6, pp. 675-695. | MR | Zbl

20. J. Gill, J. Hunt and J. Simon, Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Theoretical Computer Science, 1980, 12, pp. 333-338. | MR | Zbl

21. F. Green, J. Köbler, K. Regan, T. Schwentick and J. Torán, The power of the middle bit of a #P function, to appear in Journal of Computer and System Sciences. | MR | Zbl

22. S. Gupta, The power of witness reduction, to appear in SIAM Journal on Computing. A preliminary version appeared in Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 43-59.

23. D. Isaacson and R. Madsen, Markov Chains, Theory and Applications, Wiley and Sons, 1976. | MR | Zbl

24. B. Jenner, personal communication.

25. H. Jung, Relationships between probabilistic and deterministic tape complexity, Proc. 10th MFCS, Lecture Notes in Computer Science, 1981, 118, pp. 339-346. | MR | Zbl

26. H. Jung, On probabilistic tape complexity and fast circuits for matrix inversion problems, Proc, 11th ICALP, Lecture Notes in Computer Science, 1984, 172, pp. 281-291. | MR | Zbl

27. H. Jung, On probabilistic time and space, Proc. 12th ICALP, Lecture Notes in Computer Science, 1985, 194, pp. 310-317. | MR | Zbl

28. H. Jung, Stochastische Turingmaschinen und die Kompliziertheit arithmetischer Probleme, doctoral dissertation, Humboldt-Universität, East Berlin.

29. R. Ladner and N. Lynch, Relativization of questions about log space computability, Mathematical Systems Theory, 1976, 10, pp. 19-32. | MR | Zbl

30. R. Ladner, N. Lynch and A. Selman, A comparison of polynomial-time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. | MR | Zbl

31. I. Macarie, Space-efficient deterministic simulation of probabilistic automata, Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 109-122.

32. I. Macarie, Space-bounded probabilistic computation: old and new stories, SIGACT News Complexity Theory Column 10 (edited by Lane Hemaspaandra), SIGACT News, 1995, 26, number 3, September, pp. 2-12.

33. N. Nisan, RL ⊆ SC, Computational Complexity, 1994, 4, pp. 1-11. | MR | Zbl

34. M. Ogihara, NCk(NP) = ACk-1(NP), Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 313-324. | MR

35. M. Ogihara, The PL Hierarchy collapses, to appear in Proc. 28th STOC, 1996. | MR

36. M. Ogiwara and L. Hemachandra, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46, pp. 295-325. | MR | Zbl

37. K. Regan and T. Schwentick, On the power of one bit of a #P-function, Proc. 4th Italian Conference on Theoretical Computer Science, World Scientific Press, Singapore, 1992, pp. 317-329. See also [21]. | MR

38. P. Rossmanith, personal communication.

39. W. Ruzzo, J. Simon and M. Tompa, Space-bounded hierarchies and probabilistic computation, Journal of Computer and System Sciences, 1984, 28, pp. 216-230. | MR | Zbl

40. S. Saluja, A note on the permanent problem, Information Processing Letters, 1992, 43, pp. 1-5. | MR | Zbl

41. J. Simon, On tape-bounded probabilistic Turing machine acceptors, Theoretical Computer Science, 1981, 16, pp. 158-167. | MR | Zbl

42. J. Simon, Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th STOC, 1981, pp. 158-167.

43. J. Simon, J. Gill and J. Hunt, On tape-bounded probabilistic Turing machine transducers, Proc. 19th FOCS, 1978, pp. 107-112.

44. S. Toda, Counting problems computationally equivalent to the determinant, Technical Report CSIM 91-07, Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo, 1991.

45. S. Toda, Classes of arithmetic circuits capturing the complexity of computing the determinant, IEICE Trans. Inf. and Syst., 1992, vol. E75-D, pp. 116-124.

46. J. Torán, Complexity classes defined by counting quantifiers, Journal of the ACM, 1991, 38, pp. 753-774. | MR | Zbl

47. L. Valiant, The complexity of computing the Permanent, Theoretical Computer Science, 1979, 8, pp. 189-201. | MR | Zbl

48. L. Valiant, Why is Boolean complexity theory difficult? in Boolean Function Complexity, edited by M. S. Paterson, London Mathematical Society Lecture Notes, Series 169, Cambridge University Press, 1992. | MR | Zbl

49. V. Vinay, Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 270-284.

50. K. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. | MR | Zbl

51. C. Wilson, Relativized NC, Mathematical Systems Theory, 1987, 20, pp. 13-29. | MR | Zbl

52. C. B. Wilson, Decomposing NC and AC, SIAM Journal on Computing, 1990, 19, pp. 384-396. | MR | Zbl

53. V. Zankó, #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 1991, 2, pp. 77-82. | MR | Zbl

54. D. Zuckerman, personal communication.