論文の概要: Average-Case Reductions for $k$-XOR and Tensor PCA

• arxiv url: http://arxiv.org/abs/2601.19016v1
• Date: Mon, 26 Jan 2026 23:05:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 14:06:11.266628
• Title: Average-Case Reductions for $k$-XOR and Tensor PCA
• Title（参考訳）: k$-XOR と Tensor PCA の平均値削減
• Authors: Guy Bresler, Alina Harbuzova,
• Abstract要約: 本稿では,2つの平均ケース問題(ノイズ$kmathsftext-XOR$とPCA)について検討する。 それらの計算特性を,多時間平均ケースリダクションを用いて関連づける。
• 参考スコア（独自算出の注目度）: 5.481629070036533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study two canonical planted average-case problems -- noisy $k\mathsf{\text{-}XOR}$ and Tensor PCA -- and relate their computational properties via poly-time average-case reductions. In fact, we consider a \emph{family of problems} that interpolates between $k\mathsf{\text{-}XOR}$ and Tensor PCA, allowing intermediate densities and signal levels. We introduce two \emph{densifying} reductions that increase the number of observed entries while controlling the decrease in signal, and, in particular, reduce any $k\mathsf{\text{-}XOR}$ instance at the computational threshold to Tensor PCA at the computational threshold. Additionally, we give new order-reducing maps (e.g., $5\to 4$ $k\mathsf{\text{-}XOR}$ and $7\to 4$ Tensor PCA) at fixed entry density.
• Abstract（参考訳）: 本稿では,2つの標準植込み平均ケース問題(ノイズ$k\mathsf{\text{-}XOR}$とTensor PCA)について検討し,その計算特性を多時間平均ケース還元法を用いて検討する。 実際、$k\mathsf{\text{-}XOR}$ と Tensor PCA を補間し、中間密度と信号レベルを許容する \emph{ Family of problems} を考える。 信号の減少を制御しながら観察されたエントリ数を増加させる2つの'emph{densifying'還元を導入し、特に計算しきい値の$k\mathsf{\text{-}XOR}$インスタンスを計算しきい値のTensor PCAに還元する。 さらに、新しい順序還元写像(例えば、$5\to 4$ $k\mathsf{\text{-}XOR}$と$7\to 4$ Tensor PCA)を固定エントリー密度で与える。

関連論文リスト

• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• A Smooth Computational Transition in Tensor PCA [0.0]
  重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。 この結果から,信号対雑音比と計算コストとの間には円滑なトレードオフが認められた。
  論文  参考訳（メタデータ） (2025-09-12T00:21:20Z)
• Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
  すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。 スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
  論文  参考訳（メタデータ） (2023-02-20T18:45:24Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• 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)
• The Complexity of Sparse Tensor PCA [1.90365714903665]
  1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。 PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
  論文  参考訳（メタデータ） (2021-06-11T10:57:00Z)
• Robust Interference Management for SISO Systems with Multiple Over-the-Air Computations [16.52374405363812]
  複素数値を共有するMAC上での総和のオーバー・ザ・エア計算について考察する。 適切なTx-Rxスケーリング因子を見つけることは、$s_n$の計算における低エラーとそれによって引き起こされる干渉との間にバランスをとる。
  論文  参考訳（メタデータ） (2020-04-21T11:15:26Z)

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

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