サブ二次時間3SUMとサブ立方時間APSP

コンピュータサイエンス > データ構造とアルゴリズム arXiv:2610.06783 (cs) [2026年10月5日提出] タイトル: 三角形を用いた疎な偏ったグラフにおける真のサブ二次時間3SUMと真のサブ立方時間APSP 著者: Josh Alman, Virginia Vassilevska Williams Josh AlmanとVirginia Vassilevska Williamsによる「三角形を用いた疎な偏ったグラフにおける真のサブ二次時間3SUMと真のサブ立方時間APSP」と題された論文のPDFを表示 PDF HTML (実験的) を表示 要旨: 我々は、3SUMと全対最短経路（APSP）に対する教科書的なアルゴリズムを初めて多項式時間で改善します。具体的には、多項式サイズのn個の整数に対する3SUM問題をO(n^1.9992)時間で、多項式的に有界な整数重みを持つ有向n頂点グラフ上のAPSP問題をO(n^2.9995)時間で決定論的に解く方法を示します。これは3SUM仮説とAPSP仮説を反証するものです。既知の還元を用いることで、我々は3SUM仮説とAPSP仮説の実数値版、Exact Triangle仮説、Zero-Weight k-Clique仮説、およびvan den Brand、Nanongkai、Saranurakによる3つの矩形ヒント付きOnline Matrix--Vector予想も反証し、他の様々な問題に対しても多項式的な高速化を提供します。これらすべての結果は、細い行列積のための単一の新しいアルゴリズムから導かれます。 $N imes D$の整数行列$X$と$D imes N$の整数行列$Y$（ただし$D e N^{1/18}$）および$N^2/ ext{sqrt}(D)$以下の位置の集合$W$を考えます。我々は、$(XY)[I,J]$、$I,J otin W$の要素を$O(N^2/D^{0.063})$演算で計算します。これは、$XY$を書き出すのに必要な時間や、$N^2/ ext{sqrt}(D)$個の内積を1つずつ計算するのに必要な時間よりも多項式的に少ないです。このアルゴリズムは、Schönhageによる10回の乗算恒等式から構築されたCoppersmithの矩形行列乗算アルゴリズムの変種を修正し、$W$内の要素に必要な演算のみを実行するように設計し、少数の演算で済むことを示します。グラフアルゴリズムとして解釈すると、これは、2つの部分が$n$頂点を持つが1つの部分が$n^{ ext{epsilon}}$頂点（ただし$ ext{epsilon}<0.12$）である疎な偏った3部グラフ上で、真のサブ二次時間でAll-Edges Sparse Triangle問題を解きます。既知の還元により、Exact Triangle、したがって3SUMとAPSPは、この問題に還元されます。また、事前に知られていない単一要素の$XY$のクエリに応答するデータ構造バージョンも提供します。 コメント: 76ページ 主題: データ構造とアルゴリズム (cs.DS); 計算複雑性 (cs.CC) 引用形式: arXiv:2610.06783 [cs.DS] (またはこのバージョンについては arXiv:2610.06783v1 [cs.DS]) https://doi.org/10.48550/arXiv.2610.06783 arXiv-発行DOI (登録待ち) DataCite経由 投稿履歴 送信者: Josh Alman [メールを表示] [v1] Mon, 5 Oct 2026 17:44:29 UTC (93 KB) 全文リンク: 論文にアクセス: Josh AlmanとVirginia Vassilevska Williamsによる「三角形を用いた疎な偏ったグラフにおける真のサブ二次時間3SUMと真のサブ立方時間APSP」と題された論文のPDFを表示 PDF HTML (実験的) TeXソース ライセンスを表示 現在の閲覧コンテキスト: cs.DS < 前 | 次 > 新着 | 最近 | 2026-10 変更して以下で閲覧: cs cs.CC 参考文献と引用 NASA ADS Google Scholar Semantic Scholar BibTeX引用 読み込み中... BibTeX形式の引用 × 読み込み中... 提供データ: ブックマーク 参考文献ツール 参考文献・引用ツール 参考文献エクスプローラー トグル (エクスプローラーとは?) Connected Papers トグル (Connected Papersとは?) Litmaps トグル (Litmapsとは?) scite.ai トグル (scite Smart Citationsとは?) コード、データ、メディア この論文に関連するコード、データ、メディア alphaXiv トグル (alphaXivとは?) リンク集 コード検索 (Papers) トグル (CatalyzeXとは?) DagsHub トグル (DagsHubとは?) GotitPub トグル (GotitPubとは?) Huggingface トグル (Huggingfaceとは?) ScienceCast トグル (ScienceCastとは?) デモ デモ Replicate トグル (Replicateとは?) Spaces トグル (Hugging Face Spacesとは?) Spaces トグル (TXYZ.AIとは?) 関連論文 レコメンダーと検索ツール Influence Flower へのリンク Influence Flower (Influence Flowersとは?) COREレコメンダー トグル (CORE Recommenderとは?) 著者 会場 機関 トピック arXivLabsについて arXivLabs: コミュニティ協力者との実験的なプロジェクト arXivLabsは、協力者がarXivの新しい機能を直接ウェブサイト上で開発・共有できるフレームワークです。arXivLabsと協力する個人および組織は、オープンさ、コミュニティ、卓越性、ユーザーデータプライバシーという我々の価値観を受け入れ、遵守しています。arXivはこれらの価値観にコミットしており、それらを遵守するパートナーのみと協力します。arXivコミュニティに価値をもたらすプロジェクトのアイデアをお持ちですか？ arXivLabsについてもっと知る。 この論文の著者は誰ですか？ MathJaxを無効にする (MathJaxとは?)