EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 30 / No 1 (1996) RAIRO-Theor. Inf. Appl., 30 1 (1996) 1-21 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 30, Number 1, 1996
Page(s) 1 - 21
DOI https://doi.org/10.1051/ita/1996300100011
Published online 01 February 2017
  1. 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: 1081954] [Google Scholar]
  2. 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: 1724603] [Zbl: 0937.65150] [Google Scholar]
  3. 3. E. ALLENDER and J. JIAO, Depth reduction for noncommutative arithmetic circuits, Proc. 25th STOC, 1993, pp. 515-522. [Zbl: 1310.68097] [Google Scholar]
  4. 4. C. ÀLVAREZ, J. BALCÁZAR and B. JENNER, Adaptive logspace reducibility and parallel time, Mathematical Systems Theory, 1995, 28, pp. 117-140. [MR: 1303563] [Zbl: 0815.68054] [Google Scholar]
  5. 5. C. ÀLVAREZ and B. JENNER, A very hard log-space counting class, Theoretical Computer Science, 1993, 107, pp. 3-30. [MR: 1201163] [Zbl: 0813.68098] [Google Scholar]
  6. 6. J. BALCÁZAR, Adaptive logspace and depth-bounded reducibilities, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 240-254. [Google Scholar]
  7. 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: 760366] [Zbl: 0541.68019] [Google Scholar]
  8. 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: 750405] [Zbl: 0598.68043] [Google Scholar]
  9. 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: 996836] [Zbl: 0678.68031] [Google Scholar]
  10. 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: 1171860] [Zbl: 0825.68424] [Google Scholar]
  11. 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. [Google Scholar]
  12. 12. D. BARRINGTON, N. IMMERMAN and H. STRAUBING, On uniformity within NC1, Journal of Computer and System Sciences, 1990, 41, pp. 274-306. [MR: 1079468] [Zbl: 0719.68023] [Google Scholar]
  13. 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: 1330252] [Zbl: 0827.68040] [Google Scholar]
  14. 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: 1151340] [Zbl: 0749.68033] [Google Scholar]
  15. 15. S. COOK, A taxonomy of problems with fast parallel algorithms, Information and Control, 1985, 64, pp. 2-22. [MR: 837088] [Zbl: 0575.68045] [Google Scholar]
  16. 16. C. DAMM, DET = L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991. [Google Scholar]
  17. 17. S. FENNER, L. FORTNOW and S. KURTZ, Gap-definable counting classes, Journal of Computer and System Sciences, 1994, 48, pp. 116-148. [MR: 1259653] [Zbl: 0802.68051] [Google Scholar]
  18. 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: 0851.68029] [Google Scholar]
  19. 19. J. GILL, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 1977, 6, pp. 675-695. [MR: 464691] [Zbl: 0366.02024] [Google Scholar]
  20. 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: 589314] [Zbl: 0442.68034] [Google Scholar]
  21. 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: 1339555] [Zbl: 0849.68036] [Google Scholar]
  22. 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. [Google Scholar]
  23. 23. D. ISAACSON and R. MADSEN, Markov Chains, Theory and Applications, Wiley and Sons, 1976. [MR: 407991] [Zbl: 0332.60043] [Google Scholar]
  24. 24. B. JENNER, personal communication. [Google Scholar]
  25. 25. H. JUNG, 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] [Google Scholar]
  26. 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: 784256] [Zbl: 0583.68024] [Google Scholar]
  27. 27. H. JUNG, On probabilistic time and space, Proc. 12th ICALP, Lecture Notes in Computer Science, 1985, 194, pp. 310-317. [MR: 819266] [Zbl: 0599.68043] [Google Scholar]
  28. 28. H. JUNG, Stochastische Turingmaschinen und die Kompliziertheit arithmetischer Probleme, doctoral dissertation, Humboldt-Universität, East Berlin. [Google Scholar]
  29. 29. R. LADNER and N. LYNCH, Relativization of questions about log space computability, Mathematical Systems Theory, 1976, 10, pp. 19-32. [MR: 419190] [Zbl: 0341.68036] [Google Scholar]
  30. 30. R. LADNER, N. LYNCH and A. SELMAN, A comparison of polynomial-time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. [MR: 395319] [Zbl: 0321.68039] [Google Scholar]
  31. 31. I. MACARIE, Space-efficient deterministic simulation of probabilistic automata, Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 109-122. [Google Scholar]
  32. 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. [Google Scholar]
  33. 33. N. NISAN, RL ⊆ SC, Computational Complexity, 1994, 4, pp. 1-11. [MR: 1272773] [Zbl: 0806.68043] [Google Scholar]
  34. 34. M. OGIHARA, NCk(NP) = ACk-1(NP), Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 313-324. [MR: 1288548] [Google Scholar]
  35. 35. M. OGIHARA, The PL Hierarchy collapses, to appear in Proc. 28th STOC, 1996. [Zbl: 0922.68054] [MR: 1427501] [Google Scholar]
  36. 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: 1228809] [Zbl: 0798.68060] [Google Scholar]
  37. 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: 1254503] [Google Scholar]
  38. 38. P. ROSSMANITH, personal communication. [Google Scholar]
  39. 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: 760544] [Zbl: 0573.68021] [Google Scholar]
  40. 40. S. SALUJA, A note on the permanent problem, Information Processing Letters, 1992, 43, pp. 1-5. [MR: 1179752] [Zbl: 0780.68067] [Google Scholar]
  41. 41. J. SIMON, On tape-bounded probabilistic Turing machine acceptors, Theoretical Computer Science, 1981, 16, pp. 158-167. [MR: 632672] [Zbl: 0473.68044] [Google Scholar]
  42. 42. J. SIMON, Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th STOC, 1981, pp. 158-167. [Google Scholar]
  43. 43. J. SIMON, J. GILL and J. HUNT, On tape-bounded probabilistic Turing machine transducers, Proc. 19th FOCS, 1978, pp. 107-112. [Google Scholar]
  44. 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. [Google Scholar]
  45. 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. [Google Scholar]
  46. 46. J. TORÁN, Complexity classes defined by counting quantifiers, Journal of the ACM, 1991, 38, pp. 753-774. [MR: 1125929] [Zbl: 0799.68080] [Google Scholar]
  47. 47. L. VALIANT, The complexity of computing the Permanent, Theoretical Computer Science, 1979, 8, pp. 189-201. [MR: 526203] [Zbl: 0415.68008] [Google Scholar]
  48. 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: 1211869] [Zbl: 0769.68050] [Google Scholar]
  49. 49. V. VINAY, Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 270-284. [Google Scholar]
  50. 50. K. WAGNER, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. [MR: 853581] [Zbl: 0621.68032] [Google Scholar]
  51. 51. C. WILSON, Relativized NC, Mathematical Systems Theory, 1987, 20, pp. 13-29. [MR: 901891] [Zbl: 0627.68043] [Google Scholar]
  52. 52. C. B. WILSON, Decomposing NC and AC, SIAM Journal on Computing, 1990, 19, pp. 384-396. [MR: 1042734] [Zbl: 0692.68045] [Google Scholar]
  53. 53. V. ZANKÓ, #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 1991, 2, pp. 77-82. [MR: 1122511] [Zbl: 0739.68036] [Google Scholar]
  54. 54. D. ZUCKERMAN, personal communication. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.