論文の概要: Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

• arxiv url: http://arxiv.org/abs/2204.01665v3
• Date: Fri, 29 Mar 2024 17:27:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 14:31:02.424893
• Title: Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds
• Title（参考訳）: $\ell_\infty$ 保証付き線形ハッシュと両側カキーア境界
• Authors: Manik Dhar, Zeev Dvir,
• Abstract要約: 有限体上のランダムに選択された線型写像が $ell_infty$ の意味でよいハッシュ関数を与えることを示す。 負荷分散文献[RS98]からの既知のバウンダリにより、この結果は厳密であり、線形関数とトラリーランダム関数がエントロピー損失の定数因子であることを示す。
• 参考スコア（独自算出の注目度）: 0.8594140167290096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_\infty$ sense. More concretely, consider a set $S \subset \mathbb{F}_q^n$ and a randomly chosen linear map $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ with $q^t$ taken to be sufficiently smaller than $ |S|$. Let $U_S$ denote a random variable distributed uniformly on $S$. Our main theorem shows that, with high probability over the choice of $L$, the random variable $L(U_S)$ is close to uniform in the $\ell_\infty$ norm. In other words, {\em every} element in the range $\mathbb{F}_q^t$ has about the same number of elements in $S$ mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or $\ell_1$, distance (for a richer class of functions) as well as prior work on the expected largest 'bucket size' in linear hash functions [ADMPT99]. By known bounds from the load balancing literature [RS98], our results are tight and show that linear functions hash as well as trully random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.
• Abstract（参考訳）: 有限体上のランダムに選択された線型写像が$\ell_\infty$ の意味でよいハッシュ関数を与えることを示す。 より具体的には、集合 $S \subset \mathbb{F}_q^n$ とランダムに選択された線型写像 $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ を考える。 $U_S$は、$S$上に均一に分散されたランダム変数を表す。 我々の主定理は、$L$の選択よりも高い確率で、確率変数$L(U_S)$は$\ell_\infty$ノルムにおいて一様に近いことを示している。 言い換えれば、$\mathbb{F}_q^t$ の範囲内のすべての元は、$S$ の同じ数の元を持つ。 これは、統計学においてアナログステートメント($\ell_1$, distance (よりリッチな関数のクラス)を証明し、また線形ハッシュ関数 [ADMPT99] において期待される最大の「バケットサイズ」に関する先行研究を補完する。 負荷分散文献[RS98]からの既知のバウンダリにより、この結果は厳密であり、線形関数とトラリーランダム関数がエントロピー損失の定数因子であることを示す。 我々の証明は、線形ハッシュと有限体Kakeya問題の間の接続を利用し、この領域で開発されたツール、特に多項式法を拡張している。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
  普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。 ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T19:37:35Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  近似の性能をMonge-Kantorovich $p$-costで定量化する。 次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Learning linear dynamical systems under convex constraints [4.4351901934764975]
  線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。 A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
  論文  参考訳（メタデータ） (2023-03-27T11:49:40Z)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。 我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
  論文  参考訳（メタデータ） (2021-11-01T20:45:42Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• 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)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

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

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