論文の概要: The Planted Orthogonal Vectors Problem

• arxiv url: http://arxiv.org/abs/2505.00206v1
• Date: Wed, 30 Apr 2025 22:13:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:55.182599
• Title: The Planted Orthogonal Vectors Problem
• Title（参考訳）: 直交ベクトルの植込み問題
• Authors: David Kühnemann, Adam Polak, Alon Rosen,
• Abstract要約: 適度に選択された$p$に対して、d.$p$-biasedエントリを持つベクトル間で解を植え付ける方法を見つけ、植込みされた解が一意である。 我々の予想では、結果として生じる$k$-OVインスタンスは、解決する時間$nk-o(1)$を必要としている。
• 参考スコア（独自算出の注目度）: 4.017450863157041
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the $k$-Orthogonal Vectors ($k$-OV) problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^{o(1)}$, and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require $n^{k-o(1)}$ time in the worst case. We propose a way to \emph{plant} a solution among vectors with i.i.d. $p$-biased entries, for appropriately chosen $p$, so that the planted solution is the unique one. Our conjecture is that the resulting $k$-OV instances still require time $n^{k-o(1)}$ to solve, \emph{on average}. Our planted distribution has the property that any subset of strictly less than $k$ vectors has the \emph{same} marginal distribution as in the model distribution, consisting of i.i.d. $p$-biased random vectors. We use this property to give average-case search-to-decision reductions for $k$-OV.
• Abstract（参考訳）: k$-直交ベクトル(k$-OV)問題では、それぞれが次元$d=n^{o(1)}$の$n$二進ベクトルを含む$k$集合が与えられる。 これは細粒度複雑性の中心的な問題であり、最悪の場合、$n^{k-o(1)}$時間を必要とすると推測される。 我々は、適切に選択された$p$に対して、d.$p$-バイアス付きエントリを持つベクトル間の解を \emph{plant} する方法を提供する。 我々の予想では、結果として生じる$k$-OV のインスタンスは、解決する時間 $n^{k-o(1)}$, \emph{on average} を必要とする。 我々の植込み分布は、厳密には$k$ベクトルの任意の部分集合が、モデル分布のように、d.$p$-バイアス付きランダムベクトルからなる「emph{same}」辺分布を持つという性質を持つ。 我々はこの特性を用いて、平均ケースの探索-判定の削減を$k$-OVで提供する。

関連論文リスト

• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors [47.927989749887864]
  我々は、$s$sparseベクトルの最低ケース次元削減を超越して研究する。 任意の集合 $X$ of $s$-sparse vectors in $mathbbRO(s2)$ に対して、$mathbbRO(s2)$ への線型写像が存在し、任意の $ell_p$ ノルムにおいて$X$の99%のベクトルのノルムを正確に保存する。 我々は、$f$の非線形性と$の非負性の両方を示す。
  論文  参考訳（メタデータ） (2025-02-27T08:17:47Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
  独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。 確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
  論文  参考訳（メタデータ） (2020-10-22T17:52:45Z)
• Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
  標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。 これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
  論文  参考訳（メタデータ） (2020-04-13T08:06:29Z)

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

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