抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ストリーミングモデルにおける次のギャップサイクル計数問題を考慮して,2正則n-頂点グラフGのエッジは,ストリーム中で1対1に到着し,Gは,いくつかの小さなkに対してk-サイクルまたは2k-サイクルの互いに素な結合であると期待した。目標は,限られたメモリを用いてこれらの2つのケースを区別することである。VerbinとYu[SODA2011]はこの問題を導入し,任意の単一パスストリーミングアルゴリズムがn1-Ω(1/k)空間を必要とすることを示した。この結果は,近似MAX-CUT,マッチングサイズ,特性試験,マトリックスランクとSchattenノルム,ストリーミング一意ゲームとCSPs,および多くの他を含む,様々な問題のためのストリーミング下限の証明のために広く使用されたので,Boole Hidden Hyperマッチング通信問題を-haする。その重要性と広い応用範囲にもかかわらず,VerbinとYuの下限技術は,すべての後続結果によって継承される重要な弱点を有する:Boole Hiddenハイパーマッチング問題は,正確に1回の通信があって,実際には,2つのラウンドで対数通信で解決することができる。したがって,この問題に由来するすべてのストリーミング下限は,単一パスアルゴリズムに対してのみ保持されている。この論文の目的は,この状況を修復することである。ギャップサイクル計数問題に対して,k-サイクル対2k-サイクル対-子,k-サイクル対1ハミルトニアンサイクル-要求n{1-1/k{Ω(1/p)|}空間を区別できる,Any p-パスストリーミングアルゴリズムに対する最初のマルチパス下界を証明した。これは,VerbinとYuの研究に対する研究年代測定のこのラインにおける複数の未解決問題の進展を遂げる。この結果と事前低減の単純(または無)修正によって,著者らは,多くの以前の下限をマルチパスアルゴリズムに拡張できる。例えば,筆者らは,(1+ε)がMAX-CUTの値,最大マッチングサイズ,またはn-by-n行列のランクを近似する任意のストリーミングアルゴリズムが,nΩ(1)空間またはΩ(log(1/ε))パスのいずれかを必要とすることを,現在証明できる。これらのすべての問題に対して,事前作業は,2つのパスだけにおいてO(logn)空間アルゴリズムの可能性を開く。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】