線形分岐プログラムと指向性アフィン抽出器【JST・京大機械翻訳】

Gryaznov Svyatoslav; Pudlak Pavel; Talebanfard Navid

プレプリント

J-GLOBAL ID：202202220385405361 整理番号：22P0280157

線形分岐プログラムと指向性アフィン抽出器【JST・京大機械翻訳】

Linear Branching Programs and Directional Affine Extractors

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

読出し線形分岐プログラムの自然モデルは,クエリがF_2線形形式であり,各経路に沿って,クエリが線形に独立である分岐プログラムである。このモデルの2つの制限を考察し,ここでは,標準読取り分岐プログラムおよびパリティ決定木を一般化する,弱および強読者と呼ぶ。著者らの主な結果は,以下の通りである。方向性アフィン抽出器と呼ぶ擬似ランダムクラスの関数を定義し,これらの関数が,強い読影モデルに対して平均で困難であることを示した。次に,良好なパラメータを有するそのような関数の明示的な構築を示した。これは,パリティ決定木のためにそのような平均ケース硬度を与えるCohenとShinkar(ITCS’16)の結果を強化する。方向性アフィン抽出器は,よりよく知られたクラスのアフィン抽出器より強かった。これらの関数の重要性を考えると,著者らは,著者らの新しいクラスの関数が,独立の関心であるかもしれないことを期待する。また,線形クエリによる分解能の拡張である証明システムRes[+]を考察した。この証明システムにおけるCNFの再構成は,対応する探索問題を解く線形分岐プログラムを自然に定義する。逆に,探索問題を解く弱い読取り線形BPは,一定のブローアップでRes[+.]リフテーションに変換できることを示した。【JST・京大機械翻訳】

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

パターン認識 , システム設計・解析 , 高分子溶液・融液のレオロジー

, , ,

前のページに戻る