Arthur-Merlin games in boolean decision trees

Ran Raz; Gábor Tardos; Oleg Verbitsky; Nikolai Vereshchagin

doi:10.1006/jcss.1999.1654

Arthur-Merlin games in boolean decision trees

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai Vereshchagin

Research output: Contribution to journal › Conference article › peer-review

4 Scopus citations

Abstract

The structural properties of Arthur-Merlin games are discussed. This is motivated by the question if randomization can speed up a nondeterministic computation via a boolean decision tree. Results include connections with the block sensitivity and related combinatorial properties of a boolean function.

Original language	English (US)
Pages (from-to)	346-372
Number of pages	27
Journal	Journal of Computer and System Sciences
Volume	59
Issue number	2
DOIs	https://doi.org/10.1006/jcss.1999.1654
State	Published - Oct 1999
Externally published	Yes
Event	Proceedings of the 1998 13th Annual IEEE Conference on Computation Complexity - Buffalo, NY, USA Duration: Jun 15 1998 → Jun 18 1998

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1006/jcss.1999.1654

Cite this

@article{30a80d083ef341d3b6dba4aff8d713fe,

title = "Arthur-Merlin games in boolean decision trees",

abstract = "The structural properties of Arthur-Merlin games are discussed. This is motivated by the question if randomization can speed up a nondeterministic computation via a boolean decision tree. Results include connections with the block sensitivity and related combinatorial properties of a boolean function.",

author = "Ran Raz and G{\'a}bor Tardos and Oleg Verbitsky and Nikolai Vereshchagin",

note = "Funding Information: 1Partially supported by INTAS Grant 96-0753 and an OAD grant. Part of this work was done while visiting the Institute of Information Systems, Vienna University of Technology. 2Corresponding author.; Proceedings of the 1998 13th Annual IEEE Conference on Computation Complexity ; Conference date: 15-06-1998 Through 18-06-1998",

year = "1999",

month = oct,

doi = "10.1006/jcss.1999.1654",

language = "English (US)",

volume = "59",

pages = "346--372",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Arthur-Merlin games in boolean decision trees

AU - Raz, Ran

AU - Tardos, Gábor

AU - Verbitsky, Oleg

AU - Vereshchagin, Nikolai

N1 - Funding Information: 1Partially supported by INTAS Grant 96-0753 and an OAD grant. Part of this work was done while visiting the Institute of Information Systems, Vienna University of Technology. 2Corresponding author.

PY - 1999/10

Y1 - 1999/10

N2 - The structural properties of Arthur-Merlin games are discussed. This is motivated by the question if randomization can speed up a nondeterministic computation via a boolean decision tree. Results include connections with the block sensitivity and related combinatorial properties of a boolean function.

AB - The structural properties of Arthur-Merlin games are discussed. This is motivated by the question if randomization can speed up a nondeterministic computation via a boolean decision tree. Results include connections with the block sensitivity and related combinatorial properties of a boolean function.

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

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

U2 - 10.1006/jcss.1999.1654

DO - 10.1006/jcss.1999.1654

M3 - Conference article

AN - SCOPUS:0032597108

SN - 0022-0000

VL - 59

SP - 346

EP - 372

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

T2 - Proceedings of the 1998 13th Annual IEEE Conference on Computation Complexity

Y2 - 15 June 1998 through 18 June 1998

ER -

Arthur-Merlin games in boolean decision trees

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this