文献

J-GLOBAL ID：202002210320122558   整理番号：20A1800098

Grassmannグラフにおける非最適膨張集合について【JST・京大機械翻訳】

On non-optimally expanding sets in Grassmann graphs

著者 (5件)： Dinur Irit (Weizmann Institute of Science, Israel) ,  Khot Subhash (New York University, USA) ,  Kindler Guy (Hebrew University of Jerusalem, Israel) ,  Minzer Dor (Tel Aviv University, Israel) ,  Safra Muli (Tel Aviv University, Israel)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2018  ページ： 940-951  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Grassmannグラフにおける非拡張集合の構造を研究した。著者らは,拡張が1-δより小さいあらゆる小集合が,より小さなGrassmannグラフに同形である集合の指定リストの1つと相関しなければならないという仮説を提出する。著者らは,Grassmannグラフ上の関数を解析するためのFourier解析の枠組みを開発し,著者らの仮説が7/8以下の拡張の全ての集合に対して成立することを証明した。論文[Dinur,Khot,Kindler,MinzerおよびSafra,STOC 2018]において,線形一致仮説は,固有ゲームに対して1/2対のNP-硬度ギャップ,および他の近似性結果を意味することを示した。[Barak,KothariおよびSteurer,ECCC TR18-077]において,この研究における仮説は,[Dinur,Khot,Kindler,MinzerおよびSafra,STOC2018]の線形性一致仮説を意味することを示した。ここでの主な定理と組合わせて,これは特定のパラメータを有する線形性一致仮説のバージョンを証明した。全仮説を証明するのは,2から1と独特の制約を持つラベルカバーの新しい無条件NP硬度ギャップを得るのに当たるものである。この拡張仮説は,その完全形式[Khot,MinzerおよびSafra,ECCC TR18-006]で証明され,それによって,[Dinur,Khot,Kindler,MinzerおよびSafra,STOC2018]の一致仮説を証明し,2-to-1Games Conjecture(不完全性を有する)の証明を完了する。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： Fourier解析 ,  *ゲーム ,  線形性 ,  類似性 ,  硬度

著者キーワード (4件)： 2対2ゲーム ,  Grassmannグラフ ,  PCP ,  ユニークなゲーム

分類 (2件)： 計算理論  (JB02000A) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (3件)： グラフ ,  膨張 ,  集合