論文の概要: 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であることを示す。
関連論文リスト
- Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳(メタデータ) (2023-12-27T15:50:47Z) - The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。
おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文 参考訳(メタデータ) (2023-09-14T08:56:31Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳(メタデータ) (2022-05-27T14:50:45Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳(メタデータ) (2021-10-05T09:39:51Z) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳(メタデータ) (2020-08-14T12:17:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。