論文の概要: Collision Resistance of Single-Layer Neural Nets

• arxiv url: http://arxiv.org/abs/2606.03807v1
• Date: Tue, 02 Jun 2026 15:52:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:05.128916
• Title: Collision Resistance of Single-Layer Neural Nets
• Title（参考訳）: 単層ニューラルネットの衝突抵抗
• Authors: Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina,
• Abstract要約: 単層二層ニューラルネットワークにおける衝突のアルゴリズム的複雑性について検討する。 本研究は, 衝突抵抗の厳密な基準として, オーバーラップギャップ特性を用いた最初の研究である。
• 参考スコア（独自算出の注目度）: 3.2522957478427283
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\mathbf{A} \in \mathbb{R}^{m\times n}$, an input $\mathbf{x} \in \{-1,1\}^n$ is mapped to a binary output vector $\varphi(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$, where $\varphi$ is an activation function with constant behavior on $[κ, \infty)$ for some threshold $κ\geq 0$. We identify the threshold scale $κ=Θ(1/\sqrtα)$, where $α=m/n$, as separating two complementary phenomena. When $κ\ll 1/\sqrtα$, we give a simple online algorithm that efficiently produces extensive collisions. When $κ\gg 1/\sqrtα$, for a natural \emph{randomized} non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new ``worst-case'' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.
• Abstract（参考訳）: 単層二層ニューラルネットワークにおける衝突発見のアルゴリズム的複雑さの研究を開始する。 ランダム行列 $\mathbf{A} \in \mathbb{R}^{m\times n}$ が与えられたとき、入力 $\mathbf{x} \in \{-1,1\}^n$ はバイナリ出力ベクトル $\varphi(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$ に写像される。 しきい値のスケールは$κ=シュ(1/\sqrtα)$であり、ここでは$α=m/n$は2つの相補的な現象を分離するものである。 κ\ll 1/\sqrtα$ のとき、大規模な衝突を効率的に生成する単純なオンラインアルゴリズムを与える。 1/\sqrtα$, for a natural \emph{randomized} non- periodic activation and suitable oscillation complexity, we prove that extensive-collision space exhibit a overlap gap properties (OGP)。 衝突抵抗の厳密な基準として重なり合いギャップ特性を用いた最初の研究である。 衝突発見と平均ケースサーチの主な違いは、衝突発見が新しい ''Worst-case'' の側面を持つことである。 このような保証をスペクトル、代数的、格子的、量子的手法を含むより広範なアルゴリズムのクラスに拡張することは、まだオープンな方向のままである。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Near-optimal algorithms for private estimation and sequential testing of collision probability [1.62060928868899]
  我々は、$(alpha, beta)$-local differential privacy を満たすアルゴリズムを記述し、最大$epsilon$の誤差で衝突確率を推定する。 また、衝突確率を$epsilon$で分離した衝突確率値を区別できる逐次テストアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-18T17:12:15Z)
• 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)
• Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
  我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。 私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
  論文  参考訳（メタデータ） (2023-06-05T12:22:46Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  衝突発見は暗号解析におけるユビキタスな問題である。 本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。 応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
  論文  参考訳（メタデータ） (2022-05-27T14:50:45Z)

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

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