現実に関する低度試験【JST・京大機械翻訳】

Arora Vipul; Bhattacharyya Arnab; Fleming Noah; Kelman Esty; Yoshida Yuichi

プレプリント

J-GLOBAL ID：202202217082884940 整理番号：22P0333692

現実に関する低度試験【JST・京大機械翻訳】

Low Degree Testing over the Reals

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

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

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

関数f:R ̄n→Rが分布フリーテストモデルにおけるほとんどのdで次数の多項式であるかどうかの試験問題を研究した。ここでは,関数間の距離を,R ̄n上の未知の分布Dに関して測定し,それから,サンプルを引き出すことができた。以前の研究とは対照的に,Dは有限サポートを持つと仮定しなかった。fへのクエリアクセスを与えるテスターを設計し,Dへのサンプルアクセス,fに対する多くのクエリー(d/ε) ̄O(1)をfに,fが次数dの多項式であるならば,確率1で受信し,あらゆる次数-d多項式Pが,Dに関して少なくともεで質量のセットでfと矛盾するならば,確率を少なくとも2/3で拒絶する。結果はまた,fに対する各クエリに対する精度の多項式数のみを受信する場合,またはfがビットの対数数を用いて表現できる有理点上でのみ問うことができるとき,穏やかな仮定の下でも成立する。この方法に沿って,著者らは,独立した興味の可能性がある多変量多項式のための新しい安定性定理を証明した。【JST・京大機械翻訳】

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

グラフ理論基礎 , 計算理論

, ,

前のページに戻る