ランダム化ディシジョンツリーモデルにおける均一読取ワンス閾値公式の下限【JST・京大機械翻訳】

Leonardos Nikos

プレプリント

J-GLOBAL ID：202202220739606122 整理番号：22P0323389

ランダム化ディシジョンツリーモデルにおける均一読取ワンス閾値公式の下限【JST・京大機械翻訳】

Lower bounds for uniform read-once threshold formulae in the randomized decision tree model

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年03月31日プレプリントサーバーでの情報更新日： 2023年10月18日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

特定のクラスの読み出し閾値関数のランダム化決定木複雑性を調べた。読取り閾値公式は,根付きツリーによって定義することができ,その内部ノードは,閾値関数T_k ̄n(少なくともn入力ビットの少なくともkが1である場合のみ)でラベル付けされ,各葉は明確な変数によってラベル付けされる。そのようなツリーは自然な方法でBoole関数を定義する。基礎となる木が同一の閾値関数でラベル付けされた全ての内部ノードを持つ均一木である場合,そのような関数のランダム化決定木複雑性に焦点を当てた。dが木の深さであるc(k,n) ̄d型の下限を証明した。また,ANDとORゲートの交互レベルのツリーを別個に処理し,漸近的に最適な限界を示し,二値ケースに対する既知の限界を拡張した。【JST・京大機械翻訳】

, , , , , ,
, , , , 【Automatic Indexing@JST】

計算理論

, , , , ,

前のページに戻る