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 | |
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