Standard

Interactive protocols on the reals. / Ivanov, Sergei; De Rougemont, Michel.

STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. p. 499-510 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1373 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Ivanov, S & De Rougemont, M 1998, Interactive protocols on the reals. in STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1373 LNCS, pp. 499-510, 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98, Paris, France, 25/02/98. https://doi.org/10.1007/BFb0028585

APA

Ivanov, S., & De Rougemont, M. (1998). Interactive protocols on the reals. In STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 499-510). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1373 LNCS). https://doi.org/10.1007/BFb0028585

Vancouver

Ivanov S, De Rougemont M. Interactive protocols on the reals. In STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. p. 499-510. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/BFb0028585

Author

Ivanov, Sergei ; De Rougemont, Michel. / Interactive protocols on the reals. STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. pp. 499-510 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{6899dfdf64e04fa9832fd0b5c3e47ee1,
title = "Interactive protocols on the reals",
abstract = "We introduce the classes IPR+ (resp. IPRx) as the class of languages that admit an interactive protocol on the reals when the verifier is a BSS-machine with addition (resp. addition and multiplication). Let BIPR+ (resp. BIPRx) its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPR+ and PARR+, the class of languages accepted in parallel polynomial time coincide. In the case of multiplicative machines, we show that BIPRx ⊆ PARRx). We also separate BIP R from IPR in both models by exhibiting a language L which is not in PARRx but in IPR+. As a consequence we show that additive quantifier elimination can't be solved in PARRx and that all boolean languages are in IPR+.",
author = "Sergei Ivanov and {De Rougemont}, Michel",
year = "1998",
month = dec,
day = "1",
doi = "10.1007/BFb0028585",
language = "English",
isbn = "3540642307",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "499--510",
booktitle = "STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
note = "15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 ; Conference date: 25-02-1998 Through 27-02-1998",

}

RIS

TY - GEN

T1 - Interactive protocols on the reals

AU - Ivanov, Sergei

AU - De Rougemont, Michel

PY - 1998/12/1

Y1 - 1998/12/1

N2 - We introduce the classes IPR+ (resp. IPRx) as the class of languages that admit an interactive protocol on the reals when the verifier is a BSS-machine with addition (resp. addition and multiplication). Let BIPR+ (resp. BIPRx) its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPR+ and PARR+, the class of languages accepted in parallel polynomial time coincide. In the case of multiplicative machines, we show that BIPRx ⊆ PARRx). We also separate BIP R from IPR in both models by exhibiting a language L which is not in PARRx but in IPR+. As a consequence we show that additive quantifier elimination can't be solved in PARRx and that all boolean languages are in IPR+.

AB - We introduce the classes IPR+ (resp. IPRx) as the class of languages that admit an interactive protocol on the reals when the verifier is a BSS-machine with addition (resp. addition and multiplication). Let BIPR+ (resp. BIPRx) its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPR+ and PARR+, the class of languages accepted in parallel polynomial time coincide. In the case of multiplicative machines, we show that BIPRx ⊆ PARRx). We also separate BIP R from IPR in both models by exhibiting a language L which is not in PARRx but in IPR+. As a consequence we show that additive quantifier elimination can't be solved in PARRx and that all boolean languages are in IPR+.

UR - http://www.scopus.com/inward/record.url?scp=21944431978&partnerID=8YFLogxK

U2 - 10.1007/BFb0028585

DO - 10.1007/BFb0028585

M3 - Conference contribution

AN - SCOPUS:21944431978

SN - 3540642307

SN - 9783540642305

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 499

EP - 510

BT - STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

T2 - 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98

Y2 - 25 February 1998 through 27 February 1998

ER -

ID: 49986481