• DocumentCode
    2517608
  • Title

    Multi-oracle interactive protocols with space bounded verifiers

  • Author

    Feige, U. ; Shamir, A.

  • Author_Institution
    Dept. of Appl. Math., Weizmann Inst. of Sci., Rehovot, Israel
  • fYear
    1989
  • fDate
    19-22 Jun 1989
  • Firstpage
    158
  • Lastpage
    164
  • Abstract
    It is proved that both in the multiprover model of M. Ben-or et al. (Proc. 20th Symp. Theory Comput., 1988, p.113-131) and in the the noisy oracle model of U. Feige et al. (Proc. CRYPTO 88) a finite-state verifier can accept any recursive language. The power of verifiers with simultaneous time bounds and space bounds is considered as well
  • Keywords
    formal languages; theorem proving; finite-state verifier; interactive protocols; multiprover model; noisy oracle model; recursive language; simultaneous; space bounded verifiers; space bounds; time bounds; Collaboration; Computational modeling; Counting circuits; Game theory; History; Mathematical model; Mathematics; Protocols; Testing; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
  • Conference_Location
    Eugene, OR
  • Print_ISBN
    0-8186-1958-9
  • Type

    conf

  • DOI
    10.1109/SCT.1989.41822
  • Filename
    41822
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2517608