Weakly balanced multi-branching AND-OR trees: Reconstruction of the omitted part of Saks-Wigderson (1986) (Theory and Applications of Proof and Computation)

HANDLE オープンアクセス

この論文をさがす

抄録

We investigate variants of the Nash equilibrium for query complexity of Boolean functions. We reconstruct some omitted proofs and definitions in the paper of Saks and Wigderson (1986). In particular, by extending observation by Arimoto (2020), we introduce concepts of “weakly balanced multi-branching tree” as modified versions of “nearly balanced tree” of Saks and Wigderson, and we show recurrence formulas of randomized complexity for weakly balanced multi-branching trees.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050858441648056576
  • NII書誌ID
    AN00061013
  • HANDLE
    2433/279732
  • ISSN
    18802818
  • 本文言語コード
    en
  • 資料種別
    departmental bulletin paper
  • データソース種別
    • IRDB

問題の指摘

ページトップへ