論文の概要: Does Prior Knowledge Help Detect Collisions?

• arxiv url: http://arxiv.org/abs/2312.10196v1
• Date: Fri, 15 Dec 2023 20:50:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 12:07:24.057746
• Title: Does Prior Knowledge Help Detect Collisions?
• Title（参考訳）: 事前知識は衝突の検出に役立つか?
• Authors: Omri Ben-Eliezer, Tomer Grossman, Moni Naor,
• Abstract要約: 形状を知らないアルゴリズムと比較して,形状を知ることの助けとなる全ての局所特性を特徴付ける。 ラベルのない証明書を保持するアルゴリズムは、証明書のないアルゴリズムよりも$Theta(log n)$少ないクエリを必要とする場合もある。
• 参考スコア（独自算出の注目度）: 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). Our goal in this work is to characterize all local properties for which knowing the shape may help, compared to an algorithm that does not know the shape. Formally, we investigate the instance optimality of fundamental substructure detection problems in graphs and functions. Here, a problem is considered instance optimal (IO) if there exists an algorithm $A$ for solving the problem which satisfies that for any possible input, the (randomized) query complexity of $A$ is at most a multiplicative constant larger than the query complexity of any algorithm $A'$ for solving the same problem which also holds an unlabeled copy of the input graph or function. We provide a complete characterization of those constant-size substructure detection problems that are IO. Interestingly, our results imply that collision detection is not IO, showing that in some cases an algorithm holding an unlabeled certificate requires a factor of $\Theta(\log n)$ fewer queries than any algorithm without a certificate. We conjecture that this separation result is tight, which would make collision detection an ``almost instance optimal'' problem. In contrast, for all other non-trivial substructures, such as finding a fixed point, we show that the separation is polynomial in $n$.
• Abstract（参考訳）: 関数 $f\colon [n] \to [n]$ via (black-box) query access to the function を指定します。 衝突(ペア$x \neq y$ s.t.\ $f)のようなローカルなものを探し求めている。 (x)=f (y)$)。 問題は、関数の「形」を知ることが、あなたを助けるかどうかである(形によって、関数のいくつかの置換が知られていることを意味する)。 この研究の目標は、形状を知らないアルゴリズムと比較して、形状を知ることが役に立つ全ての局所特性を特徴づけることである。 形式的には,グラフや関数の基本部分構造検出問題のインスタンス最適性について検討する。 ここでは、任意の可能な入力に対して、A$の(ランダム化された)クエリ複雑性が、入力グラフや関数の未ラベルコピーも持つのと同じ問題を解くために、任意のアルゴリズムのクエリ複雑性よりも大きい乗法定数であることを満足するアルゴリズム$A$が存在する場合、インスタンス最適(IO)と見なされる。 我々は, IO であるこれらの定数サイズのサブ構造検出問題の完全な特徴付けを行う。 興味深いことに、我々の結果は衝突検出がIOではないことを示唆しており、ラベル付けされていない証明書を保持するアルゴリズムでは、証明書のないアルゴリズムよりも$\Theta(\log n)$少ないクエリが要求されることを示している。 この分離結果は厳密であり, 衝突検出が「最も最適」な問題となると推測する。 対照的に、不動点を見つけるような他のすべての非自明な部分構造に対して、分離は$n$の多項式であることを示す。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。