Standard

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

In: Computational Complexity, Vol. 8, No. 4, 01.01.1999, p. 330-345.

Research output: Contribution to journal › Article › peer-review

Harvard

Ivanov, S & De Rougemont, M 1999, 'Interactive protocols over the reals', Computational Complexity, vol. 8, no. 4, pp. 330-345. https://doi.org/10.1007/s000370050003

APA

Ivanov, S., & De Rougemont, M. (1999). Interactive protocols over the reals. Computational Complexity, 8(4), 330-345. https://doi.org/10.1007/s000370050003

Vancouver

Ivanov S, De Rougemont M. Interactive protocols over the reals. Computational Complexity. 1999 Jan 1;8(4):330-345. https://doi.org/10.1007/s000370050003

Author

Ivanov, Sergei ; De Rougemont, Michel. / Interactive protocols over the reals. In: Computational Complexity. 1999 ; Vol. 8, No. 4. pp. 330-345.

BibTeX

@article{9e08e8c928254fb5a874b4403ac1379c,
title = "Interactive protocols over the reals",
abstract = "We introduce the class IPℛ+ (resp. IPℛ×) 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 BIPℛ+ (resp. BIPℛ×) be its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPℛ+ and PARℛ+, the class of languages accepted in parallel polynomial time, coincide. In the case of multiplicative machines, we show that BIPℛ× ⊆ PARℛ×. We also separate BIPℛ from IPℛ in both models by exhibiting a language L which is not in PARℛ× but in IPℛ×. As a consequence we show that additive quantifier elimination cannot be solved in PARℛ× and that all boolean languages admit an interactive proof with addition and a real constant.",
keywords = "Interactive proof, Real computation",
author = "Sergei Ivanov and {De Rougemont}, Michel",
year = "1999",
month = jan,
day = "1",
doi = "10.1007/s000370050003",
language = "English",
volume = "8",
pages = "330--345",
journal = "Computational Complexity",
issn = "1016-3328",
publisher = "Birkh{\"a}user Verlag AG",
number = "4",

}

RIS

TY - JOUR

T1 - Interactive protocols over the reals

AU - Ivanov, Sergei

AU - De Rougemont, Michel

PY - 1999/1/1

Y1 - 1999/1/1

N2 - We introduce the class IPℛ+ (resp. IPℛ×) 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 BIPℛ+ (resp. BIPℛ×) be its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPℛ+ and PARℛ+, the class of languages accepted in parallel polynomial time, coincide. In the case of multiplicative machines, we show that BIPℛ× ⊆ PARℛ×. We also separate BIPℛ from IPℛ in both models by exhibiting a language L which is not in PARℛ× but in IPℛ×. As a consequence we show that additive quantifier elimination cannot be solved in PARℛ× and that all boolean languages admit an interactive proof with addition and a real constant.

AB - We introduce the class IPℛ+ (resp. IPℛ×) 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 BIPℛ+ (resp. BIPℛ×) be its restriction when only boolean messages can be exchanged between the prover and the verifier. We prove that the classes BIPℛ+ and PARℛ+, the class of languages accepted in parallel polynomial time, coincide. In the case of multiplicative machines, we show that BIPℛ× ⊆ PARℛ×. We also separate BIPℛ from IPℛ in both models by exhibiting a language L which is not in PARℛ× but in IPℛ×. As a consequence we show that additive quantifier elimination cannot be solved in PARℛ× and that all boolean languages admit an interactive proof with addition and a real constant.

KW - Interactive proof

KW - Real computation

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

U2 - 10.1007/s000370050003

DO - 10.1007/s000370050003

M3 - Article

AN - SCOPUS:0033265340

VL - 8

SP - 330

EP - 345

JO - Computational Complexity

JF - Computational Complexity

SN - 1016-3328

IS - 4

ER -

ID: 49986392