抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
Yao(1977)の精巧なミニマックス原理は,有限領域を有する任意のBoole-値関数fに対して,fの入力に対するfの誤差εへの計算fが,最悪ケース入力における誤差εに対する計算fのちょうどハードであるように,fのドメイン上の分布μがある。しかし,分布μは,ターゲット誤差レベルεに依存する:有界誤差に対して緊密であるハード分布は,小さなバイアスに解決するのに自明であり,そして,小さなバイアスレベルに対して緊密であるハード分布は,有界誤差レベルに対して,緊密から遠いかもしれない。本研究では,1回全てのバイアスレベルに対して働くハード分布μを与えることができる新しいタイプのミニマックス定理を導入した。ランダム化クエリ複雑性,ランダム化通信複雑性,いくつかのランダム化回路モデル,量子クエリーおよび通信複雑性,近似多項式度,および近似ログランクに対して,この仕事が,この仕事を示した。また,著者らは,Impaglazzoのハードコア補助定理の改良版を証明した。著者らの証明は,Von Neumannのミニマックス定理または線形プログラミング双対性を用いる古典的手法に関する2つの革新に依存する。最初に,Sionのミニマックス定理を用いて,アルゴリズムのコストとスコアを表す双線形関数の比率に対するミニマックス定理を証明した。第2に,適切なスコアリング規則によって評価された「予測アルゴリズム」としてそれらを見ることによって,低バイアスランダム化アルゴリズムを分析する新しい方法を導入した。ランダム化アルゴリズムの予測バージョンの期待スコアは,アルゴリズムのバイアスを分析するより細かい方法であると思われる。そのような期待したスコアは,多くの優れた数学的特性を持ち,例えば,それらは,二次的な代わりに線形的に増幅できる。予測アルゴリズムは,小バイアスアルゴリズムの細粒解析を必要とする将来の研究での使用を見出すであろう。【JST・京大機械翻訳】
