@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},
volume = {30},
year = {1996},
pages = {1-21},
mrnumber = {1398856},
zbl = {0851.68033},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 1-21. http://gdmltest.u-ga.fr/item/ITA_1996__30_1_1_0/
1. , 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 1081954
2. , and , The complexity of matrix rank and feasible systems of linear equations, to appear in Proc. 28th STOC, 1996. | MR 1724603 | Zbl 0937.65150
3. and , Depth reduction for noncommutative arithmetic circuits, Proc. 25th STOC, 1993, pp. 515-522.
4. , and , Adaptive logspace reducibility and parallel time, Mathematical Systems Theory, 1995, 28, pp. 117-140. | MR 1303563 | Zbl 0815.68054
5. and , A very hard log-space counting class, Theoretical Computer Science, 1993, 107, pp. 3-30. | MR 1201163 | Zbl 0813.68098
6. , Adaptive logspace and depth-bounded reducibilities, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 240-254.
7. , On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 1984, 18, pp. 147-150. | MR 760366 | Zbl 0541.68019
8. , and , Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, 1983, 48, pp. 113-136. | MR 750405 | Zbl 0598.68043
9. , , , and , Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18, pp. 559-578. | MR 996836 | Zbl 0678.68031
10. , , and , An optimal parallel algorithm for formula evaluation, SIAM Journal on Computing, 1992, 21, pp. 755-780. | MR 1171860 | Zbl 0825.68424
11. and , Zero-one permanent is #P-complete, a simpler proof, Proc. 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93), IEEE press.
12. , and , On uniformity within NC1, Journal of Computer and System Sciences, 1990, 41, pp. 274-306. | MR 1079468 | Zbl 0719.68023
13. , and , PP is closed under intersection, Journal of Computer and System Sciences, 1995, 50, pp. 191-202. | MR 1330252 | Zbl 0827.68040
14. , , and , Structure and Importance of Logspace MOD-Classes, Mathematical Systems Theory, 1992, 25, pp. 223-237. | MR 1151340 | Zbl 0749.68033
15. , A taxonomy of problems with fast parallel algorithms, Information and Control, 1985, 64, pp. 2-22. | MR 837088 | Zbl 0575.68045
16. , DET = L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991.
17. , and , Gap-definable counting classes, Journal of Computer and System Sciences, 1994, 48, pp. 116-148. | MR 1259653 | Zbl 0802.68051
18. and , PP is closed under truth-table reductions, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 13-15. | Zbl 0851.68029
19. , Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 1977, 6, pp. 675-695. | MR 464691 | Zbl 0366.02024
20. , and , Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Theoretical Computer Science, 1980, 12, pp. 333-338. | MR 589314 | Zbl 0442.68034
21. , , , and , The power of the middle bit of a #P function, to appear in Journal of Computer and System Sciences. | MR 1339555 | Zbl 0849.68036
22. , 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. and , Markov Chains, Theory and Applications, Wiley and Sons, 1976. | MR 407991 | Zbl 0332.60043
24. , personal communication.
25. , Relationships between probabilistic and deterministic tape complexity, Proc. 10th MFCS, Lecture Notes in Computer Science, 1981, 118, pp. 339-346. | MR 652767 | Zbl 0462.68031
26. , 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 784256 | Zbl 0583.68024
27. , On probabilistic time and space, Proc. 12th ICALP, Lecture Notes in Computer Science, 1985, 194, pp. 310-317. | MR 819266 | Zbl 0599.68043
28. , Stochastische Turingmaschinen und die Kompliziertheit arithmetischer Probleme, doctoral dissertation, Humboldt-Universität, East Berlin.
29. and , Relativization of questions about log space computability, Mathematical Systems Theory, 1976, 10, pp. 19-32. | MR 419190 | Zbl 0341.68036
30. , and , A comparison of polynomial-time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. | MR 395319 | Zbl 0321.68039
31. , Space-efficient deterministic simulation of probabilistic automata, Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 109-122.
32. , 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. , RL ⊆ SC, Computational Complexity, 1994, 4, pp. 1-11. | MR 1272773 | Zbl 0806.68043
34. , NCk(NP) = ACk-1(NP), Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 313-324. | MR 1288548
35. , The PL Hierarchy collapses, to appear in Proc. 28th STOC, 1996. | MR 1427501
36. and , A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46, pp. 295-325. | MR 1228809 | Zbl 0798.68060
37. and , 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 1254503
38. , personal communication.
39. , and , Space-bounded hierarchies and probabilistic computation, Journal of Computer and System Sciences, 1984, 28, pp. 216-230. | MR 760544 | Zbl 0573.68021
40. , A note on the permanent problem, Information Processing Letters, 1992, 43, pp. 1-5. | MR 1179752 | Zbl 0780.68067
41. , On tape-bounded probabilistic Turing machine acceptors, Theoretical Computer Science, 1981, 16, pp. 158-167. | MR 632672 | Zbl 0473.68044
42. , Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th STOC, 1981, pp. 158-167.
43. , and , On tape-bounded probabilistic Turing machine transducers, Proc. 19th FOCS, 1978, pp. 107-112.
44. , 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. , Classes of arithmetic circuits capturing the complexity of computing the determinant, IEICE Trans. Inf. and Syst., 1992, vol. E75-D, pp. 116-124.
46. , Complexity classes defined by counting quantifiers, Journal of the ACM, 1991, 38, pp. 753-774. | MR 1125929 | Zbl 0799.68080
47. , The complexity of computing the Permanent, Theoretical Computer Science, 1979, 8, pp. 189-201. | MR 526203 | Zbl 0415.68008
48. , 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 1211869 | Zbl 0769.68050
49. , Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 270-284.
50. , The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. | MR 853581 | Zbl 0621.68032
51. , Relativized NC, Mathematical Systems Theory, 1987, 20, pp. 13-29. | MR 901891 | Zbl 0627.68043
52. , Decomposing NC and AC, SIAM Journal on Computing, 1990, 19, pp. 384-396. | MR 1042734 | Zbl 0692.68045
53. , #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 1991, 2, pp. 77-82. | MR 1122511 | Zbl 0739.68036
54. , personal communication.