文献

J-GLOBAL ID：202202235254748818   整理番号：22A0917412

アプリケーションを持つマルチスライスのための不変性原理【JST・京大機械翻訳】

An Invariance Principle for the Multi-slice, with Applications

著者 (4件)： Braverman Mark (Princeton University,Department of Computer Science,Princeton,USA) ,  Khot Subhash (Courant Institute of Mathematical Sciences, New York University,Department of Computer Science,New York,USA) ,  Lifshitz Noam (The Hebrew University of Jerusalem,Department of Mathematics,Jerusalem,Israel) ,  Minzer Dor (MIT,Department of Mathematics,Cambridge,USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 228-236  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 定数としてアルファベットサイズm→N思考と,nのエントリー和がnのエントリー和であるk=(k_1,k_m)を考えると,k-マルチスライスは,各シンボルi||[m]が正確にk_i時間に現れるベクトルx→∞[m]nの集合である。μ(i)=k_i/nの積空間([m]n,μn)上で機能するために,マルチスライス上の低度関数に対する不変性原理を示した。この回答は[21]によって提起された疑問である。不変性原理の応用として,筆者らは,1)「ディケータシップテストのアナログ」が,あるクラスのディクターシップテストに対して,完全な完全性を持つ問題に対する計算硬度パラダイムを意味することを示した。著者らの計算硬度は,Rich 2to-1 Games Conjectureと呼ばれるユニークなGames Conjectureの最近の強化を仮定して証明された。このアナログを用いて,Rich 2-to-1 Games Conjectureを仮定すると,(a)CSPの充足可能なインスタンスを識別するためのNP困難であり,最もfrac2r+1{2{r}+o(1)充足可能であり,(b)3色可能なグラフを識別すること,および,サイズo(1)の独立集合を含まないグラフを識別できるという,r-ary CSP P_rが存在することを示す。2)相関,製品空間に関する機能の製品の期待を研究するために,マルチスライス上の機能の製品の期待を研究する問題の低減。特に,マルチスライスに対して[38]からGauss限界のアナログを推論できる。3)コンパニオン論文において,著者らは,極値結合器における著者らの不変性原理の更なる応用を示し,より具体的には,マッチングのよく研究されたケースの自然な拡張であるζ-森林と呼ばれるハイパーグラフHの幅広いファミリーの除去補助定理を証明した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ベクトル ,  結合器 ,  アナログ系 ,  *応用プログラム ,  硬度 ,  *不変性 ,  完全性 ,  超グラフ ,  NP困難
準シソーラス用語： マルチスライス , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： アプリケーション ,  マルチスライス ,  不変性 ,  原理