Arthur-Merlin games in boolean decision trees

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

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


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 languageEnglish (US)
Pages (from-to)346-372
Number of pages27
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Oct 1999
Externally publishedYes
EventProceedings of the 1998 13th Annual IEEE Conference on Computation Complexity - Buffalo, NY, USA
Duration: Jun 15 1998Jun 18 1998

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Arthur-Merlin games in boolean decision trees'. Together they form a unique fingerprint.

Cite this