Computational limitations of Stochastic Turing machines and Arthur-Merlin games with small space bounds

1. L. Babai, Trading Group Theory for Randomness, Proc. 17. ACM Symp. on Theory of Computing, 1985, 421–429.

   Google Scholar 

2. B. von Braunmiihl, R. Gengler, R. Rettinger The Alternation Hierarchy for Machines with Sublogarithmic Space is Infinite, Comp. Compl. 3, 1993, 207–230.

   Article  Google Scholar 

3. A. Chandra, D. Kozen, L. Stockmeyer, Alternation, J. ACM 28, 1981, 114–133.

   Article  Google Scholar 

4. A. Condon, Computational Model of Games, MIT Press, 1989.

   Google Scholar 

5. A. Condon, The Complexity of Space Bounded Interactive Proof Systems, in Complexity Theory: Current Research, S. Homer, U. Schöning, K. Ambos-Spies (Eds.), Cambridge Univ. Press, 1993, 147–190.

   Google Scholar 

6. A. Condon, R. Lipton, On the Complexity of Space Bounded Interactive Proofs, Proc. 30. IEEE Symp. on Found. of Comp. Science, 1989, 462–467.

   Google Scholar 

7. A. Condon, L. Hellerstein, S. Pottle, A. Wigderson, On the Power of Finite Automata with both Nondeterministic and Probabilistic States, Proc. 26. ACM Symp. on Theory of Computing, 1994, 676–685.

   Google Scholar 

8. S. Dwork, L. Stockmeyer, Finite State Verifiers L the Power of Interaction, J. ACM 39, 1992, 800–828.

   Article  Google Scholar 

9. R. Freivalds, Fast Probabilistic Algorithms, Proc. 8. Int. Symp. on Math. Found. of Comp. Science, 1979, LNCS, 57–69.

   Google Scholar 

10. R. Freivalds, Probabilistic 2-way Machines, Proc. 10. Int. Symp. on Math. Found. of Comp. Science, 1981, LNCS, 33–45.

    Google Scholar 

11. R. Freivalds, M. Karpinski, Lower Space Bounds for Randomized Computation, Proc. 21. EATCS Int. Colloq. on Automata, Languages, and Programming, 1994, LNCS, 580–592.

    Google Scholar 

12. V. Geffert, A Hierarchy that Does not Collaps: Alternation in Low Level Space, Theo. Information and Applications 28, 1994, 465–512.

    Google Scholar 

13. A. Greenberg, A. Weiss, A Lower Bound for Probabilistic Algorithms for Finite State Machines, J. Comput. Syst. Sci. 33, 1986, 88–105.

    Article  Google Scholar 

14. J. Gill, Computational Complexity of Probabilistic Turing Machines, SIAM J. Computing 7, 1977, 675–695.

    Article  Google Scholar 

15. S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM J. Computing 18, 1989, 186–208.

    Article  Google Scholar 

16. S. Goldwasser, M. Sipser, Private Coins versus Public Coins in Interactive Proof Systems, Proc. 18. ACM Symp. on Theory of Computing, 1986, 59–68.

    Google Scholar 

17. K. Iwama, ASpace (o(log log n)) is Regular, SIAM J. Computing 22,1993,136–146.

    Article  Google Scholar 

18. M. Liśkiewicz, Interactive Proof Systems with Public Coins: Lower Space Bounds and Hierarchies of Complexity Classes, ICSI Technical Report 1996, also Proc. 14. GI-AFCET Symp. on Theo. Aspects of Comp. Science, 1997, LNCS 1200,129–140.

    Google Scholar 

19. M. Liskiewicz, R. Reischuk, Separating the Lower Levels of the Sublogarithmic Space Hierarchy, Proc. 10. GI-AFCET Symp. on Theo. Aspects of Comp. Science, 1993, LNCS, 16–27.

    Google Scholar 

20. M. Liskiewicz, R. Reischuk, The Sublogarithmic Alternating Space World, SIAM J. Computing 24, 1996, 828–861.

    Article  Google Scholar 

21. M. Liskiewicz and R. Reischuk, Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds, ICSI Technical Report No. TR-96-025, Berkeley, July 1996.

    Google Scholar 

22. M. Liskiewicz and R. Reischuk, Separating Small Space Complexity Classes of Stochastic Turing Machines, Technical Report Informatik/Mathematik A-96-17, Med. Universität zu Lℏeck, November 1997.

    Google Scholar 

23. M. Liskiewicz and R. Reischuk, Computing with Sublogarithmic Space, in Complexity Theory Retrospective II, A. Selman, L. Hemaspaandra (Eds), Springer Verlag, 1997.

    Google Scholar 

24. I. Macarie, Space-bounded Probabilistic Computation: Old and New Stories, SIGACT News 26, 1995, 2–12.

    Article  Google Scholar 

25. C. Papadimitriou, Games against Nature, J. CSS 31, 1985, 288–301.

    Google Scholar 

Download references