article

Free access

Space-bounded probabilistic game automata

Author:

Anne CondonAuthors Info & Claims

Journal of the ACM (JACM), Volume 38, Issue 2

Pages 472 - 494

https://doi.org/10.1145/103516.128681

Published: 01 April 1991 Publication History

PDF eReader

References

[1]

BABAI, L. Trading group theory for randomness. In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 421-429.

Crossref

Google Scholar

[2]

BEN-OR, M., GOLDWASSER, S., AND WIGDERSON, A. Completeness theorems for non-crytographic fault-tolerant distributed computation. In Proceedings of the 20th A CM Symposium on the Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, 1988, pp. 1-10.

Crossref

Google Scholar

[3]

BRASSARD, G., AND CREPEAU, C Nontransitive transfer of confidence: A perfect-zero knowledge protocol for SAT and beyond. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1986, 188-195.

Google Scholar

[4]

CHANDRA, A. K., KOZEN, D. C., AND STOCKMEYER, L. J. Alternaoon. J. A CM. 28, 1 (Jan. 1981), 114-133.

Crossref

Google Scholar

[5]

CHAUM, D., CREPEAU, C., AND DAMGARD, I. Multiparty unconditionally secure protocols. In Proceedings of the 20th A CM Symposium on the Theory of Computing (Chicago, Ill., May 2-4), ACM, New York, 1988, 11-19.

Crossref

Google Scholar

[6]

CONDON, A. :Space bounded probabllistic game automata. In Conference on Structure in Complexity Theory (June). IEEE, New York, 1988, pp. 162-174.

Google Scholar

[7]

CONDON, A.The complexity of stochastic games. Tech. Rep. 863. Univ. Wisconsin-Madison, Madison, Wis., 1989.

Google Scholar

[8]

CONDON, A. Computational Models of Games. MIT Press, Cambridge, Mass., 1989.

Google Scholar

[9]

CONDON, A, AND LADNER, R. Probabilistic game automata. J. Comput. Syst. Sci. 36, 3 (June 1988), 452-489.

Crossref

Google Scholar

[10]

CONDON, A., AND LIPTON, R. J. On the complexity of space bounded interactive proof systems. In Proceedings of the 30th IEEE Symposium on the Foundauons of Computer Science (Oct.). IEEE, New York, 1989, pp. 462-467.

Google Scholar

[11]

DWORK, C. AND STOCKMEYER, L. Interacnve proof systems with finite state verifiers. Res. Rep. RJ 6262 (61659). IBM Almaden Research Center, San Jose, Calif., 1988.

Google Scholar

[12]

FEIGE, U., FIAT, A., AND SHAMIR, A. Zero knowledge proofs of identity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM, New York, 1987, pp. 210-217.

Crossref

Google Scholar

[13]

FORTNOW, L. Complexity-theoretic aspects of interactive proof systems. Tech. Rep. MIT/LCS/TR-447. MIT, Cambridge, Mass., 1989.

Google Scholar

[14]

FORTNOW, L., AND SIPSER, M. Interactive proof systems with a log space verifier. Manuscript. MIT, Cambridge, Mass., 1988.

Google Scholar

[15]

GAREY. M. R., AND JOHNSON, D. S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.

Crossref

Google Scholar

[16]

GOLDREICH, 0., MICALI, S., AND WIGDERSON, A Proofs that yield nothing but their validity and a methodology of cryptographic design. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1986, pp. 174-187.

Google Scholar

[17]

GOLDWASSER, S., AND MICALI, S. Probabflistic encryption and how to play mental poker keeping secret all partial information. In Proceedings of the 14th A CM Symposium on the Theory of Computing (San Francisco, Cahf., May 5-7). ACM, New York, 1982, pp. 365-377.

Crossref

Google Scholar

[18]

GOLDWASSER, S., MICALI, S., AND RACKOFF, C. The knowledge complexity of interactive proof systems. In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 291-304.

Crossref

Google Scholar

[19]

GOLDWASSER, S., AND SIPSER, M. Private coins versus pubhc coins in interactive proof systems. In Proceedings of the 18th ACM Symposium on the Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, 1986, pp. 59-68.

Crossref

Google Scholar

[20]

KILLIAN, J. Zero knowledge with log-space verifiers. In Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1988, pp. 25-35.

Google Scholar

[21]

PAPADIMITRIOU, C. H. Games against nature. J Comput. Syst. Sct. 31 (1985), 288-301

Crossref

Google Scholar

[22]

PETERSON, G. L., AND REIF, J. H. Multiple person alternation. In Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1979, pp. 348-363.

Google Scholar

[23]

REIF, J H. The complexity of two-player games of incomplete reformation J. Comput. Syst. Sci. 29, 2 (1984), 274-301

Google Scholar

[24]

Ruzzo, W. L., SIMON, J., AND TOMPA, M. Space-bounded hierarchies and probabflistlc computatlons. J. Comput. Sys. Scl. 28, 2 (Apr. 1984), 216-230.

Google Scholar

[25]

SHAPLEY, L. S. Stochastic games. In Proceedings of the National Academy of Sciences, U.S.A. Vol, 39. 1953, pp. 1095-1100.

Google Scholar

[26]

TOMPA, M., AND WOLL, H Random self-reducibility and zero-knowledge interactive proofs of possession of informaUon. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1987, pp. 472-482.

Google Scholar

[27]

VRIEZE, 0. J. Stochastic games with finite state and action spaces, CWI Tract 33. Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, I987.

Google Scholar

Cited By

View all

Hartisch MLorenz U(2019)Mastering Uncertainty: Towards Robust Multistage Optimization with Decision Dependent UncertaintyPRICAI 2019: Trends in Artificial Intelligence10.1007/978-3-030-29908-8_36(446-458)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29908-8_36
Dwork CNaor MRothblum G(2016)Spooky Interaction and Its DiscontentsProceedings, Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981610.1007/978-3-662-53015-3_5(123-145)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53015-3_5
Goldwasser SKalai YRothblum G(2015)Delegating ComputationJournal of the ACM10.1145/269943662:4(1-64)Online publication date: 11-Sep-2015
https://dl.acm.org/doi/10.1145/2699436
Show More Cited By

Index Terms

Space-bounded probabilistic game automata
1. Theory of computation

Recommendations

Finite state verifiers I: the power of interaction
An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown:
- (1) IPSs in which the verifier uses private randomization are strictly more powerful ...
Affine Automata Verifiers
Unconventional Computation and Natural Computation
Abstract
We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted ...
Generalized quantum arthur-merlin games
CCC '15: Proceedings of the 30th Conference on Computational Complexity

This paper investigates the role of interaction and coins in quantum Arthur-Merlin games(also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 38, Issue 2

April 1991

260 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/103516

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1991

Published in JACM Volume 38, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
744
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)9

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hartisch MLorenz U(2019)Mastering Uncertainty: Towards Robust Multistage Optimization with Decision Dependent UncertaintyPRICAI 2019: Trends in Artificial Intelligence10.1007/978-3-030-29908-8_36(446-458)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29908-8_36
Dwork CNaor MRothblum G(2016)Spooky Interaction and Its DiscontentsProceedings, Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981610.1007/978-3-662-53015-3_5(123-145)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53015-3_5
Goldwasser SKalai YRothblum G(2015)Delegating ComputationJournal of the ACM10.1145/269943662:4(1-64)Online publication date: 11-Sep-2015
https://dl.acm.org/doi/10.1145/2699436
Demirci HSay AYakaryılmaz A(2015)The Complexity of Debate CheckingTheory of Computing Systems10.1007/s00224-014-9547-757:1(36-80)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00224-014-9547-7
Say AYakaryılmaz A(2012)Finite state verifiers with constant randomnessProceedings of the 8th Turing Centenary conference on Computability in Europe: how the world computes10.1007/978-3-642-30870-3_65(646-654)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30870-3_65
Goldwasser SKalai YRothblum GLadner RDwork C(2008)Delegating computationProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374396(113-122)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374396
Aumann YDing YRabin M(2006)Everlasting security in the bounded storage modelIEEE Transactions on Information Theory10.1109/TIT.2002.100384548:6(1668-1680)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TIT.2002.1003845
Ergün FKumar RRubinfeld R(2004)Fast approximate probabilistically checkable proofsInformation and Computation10.1016/j.ic.2003.09.005189:2(135-159)Online publication date: 15-Mar-2004
https://dl.acm.org/doi/10.1016/j.ic.2003.09.005
Ding Y(2001)Oblivious Transfer in the Bounded Storage ModelAdvances in Cryptology — CRYPTO 200110.1007/3-540-44647-8_9(155-170)Online publication date: 2-Aug-2001
https://doi.org/10.1007/3-540-44647-8_9
Ergün FKumar RRubinfeld RVitter JLarmore LLeighton T(1999)Fast approximate PCPsProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301267(41-50)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301250.301267
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Finite state verifiers I: the power of interaction

Affine Automata Verifiers

Generalized quantum arthur-merlin games

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations