抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
低度多項式をテストする問題は,理論的コンピュータ科学における重要性,特に複雑性理論において,その年にわたって大きな注目を受けてきた。問題は3つのパラメータによって指定される:フィールドサイズq,度dと近接パラメータδ,および目標は与えられた関数に対するできるだけ少ないクエリーとして,与えられた関数が大部分のdで度を持ち,与えられた関数が任意の程度d関数からδ-farである場合を識別できる,ある関数に対する可能なクエリーとして,テスター作成を設計することである。テスターは,もしO(q ̄d+1/δ)クエリ(必要と知られている)を作るならば,最適と呼ばれる。サイズqの場に対して,自然のt-フラットテスターは,q=2に対してBhattacharyyaらによって最適であり,その後,すべてのプライムパワーqに対してHaramatyらによって最適であることを示した。しかし,場サイズへの依存性は塔型関数である。上記の結果を改善し,場サイズへの依存性が多項式であることを示した。また,この手法は,揚力付きアフィン不変符号のより一般的な設定にも適用され,f|_Aがdより大きいような部分空間Aのような誤り部分空間の収集の構造を研究することに基づいている。この目的に向けて,著者らは,これらの集合がGrassmannグラフのアフィンバージョンにおいてあまり拡大せず,大域的超収縮性を介してそれらに関する構造結果を確立するために使用することを観察した。次に,この構造を用いてf上の局所補正を行った。【JST・京大機械翻訳】