論文の概要: On the instance optimality of detecting collisions and subgraphs
- arxiv url: http://arxiv.org/abs/2312.10196v2
- Date: Fri, 2 Aug 2024 16:57:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-05 18:33:20.477490
- Title: On the instance optimality of detecting collisions and subgraphs
- Title（参考訳）: 衝突と部分グラフの検出のインスタンス最適性について
- Authors: Omri Ben-Eliezer, Tomer Grossman, Moni Naor,
- Abstract要約: グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。
アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。
この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
- 参考スコア（独自算出の注目度）: 7.055459105099637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Suppose you are given a function $f\colon [n] \to [n]$ via (black-box) query access to the function. You are looking to find something local, like a collision (a pair $x \neq y$ s.t. $f(x)=f(y)$). The question is whether knowing the "shape" of the function helps you or not (by shape we mean that some permutation of the function is known). Formally, we investigate the unlabeled instance optimality of substructure detection problems in graphs and functions. A problem is $g(n)$-instance optimal if it admits an algorithm $A$ satisfying that for any possible input, the (randomized) query complexity of $A$ is at most $g(n)$ times larger than the query complexity of any algorithm $A'$ which solves the same problem while holding an unlabeled copy of the input (i.e., any $A'$ that "knows the structure of the input"). Our results point to a trichotomy of unlabeled instance optimality among substructure detection problems in graphs and functions: 1. A few very simple properties have an $O(1)$-instance optimal algorithm. 2. Most properties of graphs and functions, with examples such as containing a fixed point or a $3$-collision in functions, or a triangle in graphs, are $n^{\Omega(1)}$-far from instance optimality. 3. The problems of collision detection in functions and finding a claw in a graph serve as a middle ground between the two regimes. We show that these two properties are $\Omega(\log n)$-far from instance optimality, and conjecture that this bound is tight. We provide evidence towards this conjecture, by proving that finding a claw in a graph is $O(\log(n))$-instance optimal among all input graphs for which the query complexity of an algorithm holding an unlabeled certificate is $O\left(\sqrt{\frac{n}{\log n}}\right)$.
- Abstract（参考訳）: 関数 $f\colon [n] \to [n]$ via (black-box) query access to the function を指定します。
衝突(ペア$x \neq y$ s.t. $f)のようなローカルなものを探し求めている。
(x)=f
(y)$)。
問題は、関数の「形」を知ることが、あなたを助けるかどうかである(形によって、関数のいくつかの置換が知られていることを意味する)。
本稿では,グラフや関数のサブ構造検出問題のラベルなしインスタンス最適性について検討する。
可能な入力に対して、$A$の(ランダム化された)クエリの複雑さが、任意のアルゴリズムのクエリの複雑さの少なくとも1倍の$g(n)$であることを満たすアルゴリズムを許容すると、$g(n)$-instance 最適である。
この結果から,グラフや関数のサブ構造検出問題における未ラベルのインスタンス最適性の三分法が示唆された: 1. 非常に単純な性質のいくつかは,$O(1)$-instanceの最適アルゴリズムを持つ。
2. グラフと関数のほとんどの性質は、不動点や関数の3$コリションを含む例やグラフの三角形のような例は、インスタンス最適性から$n^{\Omega(1)}$-farである。
3. 関数における衝突検出の問題とグラフ内の爪の発見は, 両者の中間となる。
この2つの性質は、インスタンス最適性から$\Omega(\log n)$-farであることを示し、この境界がきついことを予想する。
この予想に対する証拠として、グラフ内の爪を見つけることは、未ラベル証明書を持つアルゴリズムのクエリ複雑性が$O\left(\sqrt{\frac{n}{\log n}}\right)$である全ての入力グラフの中で最適な$O(\log(n))$-instanceであることを示す。
関連論文リスト
- The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Verification and search algorithms for causal DAGs [11.038866111306728]
クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-30T15:52:30Z) - Sample Complexity of Learning Heuristic Functions for Greedy-Best-First
and A* Search [15.191184049312467]
Greedy best-first search (GBFS) と A* search (A*) は、大きなグラフ上でパスフィニングを行うための一般的なアルゴリズムである。
GBFS と A* の学習関数のサンプル複雑性について検討した。
整数重み条件下でのGBFS と A* の境界は、$lg n$ factor まで厳密であることを示す。
論文 参考訳（メタデータ） (2022-05-20T04:57:35Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。