論文の概要: Higher rank antipodality

• arxiv url: http://arxiv.org/abs/2307.16857v2
• Date: Thu, 30 Nov 2023 13:01:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-01 23:08:26.507867
• Title: Higher rank antipodality
• Title（参考訳）: 高位対足性
• Authors: M\'arton Nasz\'odi and Zsombor Szil\'agyi and Mih\'aly Weiner
• Abstract要約: 一般確率論に動機づけられて、集合 $X$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。 k=1$ の場合、Klee が導入した(ペアワイズで)反ポッド性の概念と一致する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by general probability theory, we say that the set $X$ in $\mathbb{R}^d$ is \emph{antipodal of rank $k$}, if for any $k+1$ elements $q_1,\ldots q_{k+1}\in X$, there is an affine map from $\mathrm{conv} X$ to the $k$-dimensional simplex $\Delta_k$ that maps $q_1,\ldots q_{k+1}$ onto the $k+1$ vertices of $\Delta_k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee. We consider the following natural generalization of Klee's problem on antipodal sets: What is the maximum size of an antipodal set of rank $k$ in $\mathbb{R}^d$? We present a geometric characterization of antipodal sets of rank $k$ and adapting the argument of Danzer and Gr\"unbaum originally developed for the $k=1$ case, we prove an upper bound which is exponential in the dimension. We point out that this problem can be connected to a classical question in computer science on finding perfect hashes, and it provides a lower bound on the maximum size, which is also exponential in the dimension.
• Abstract（参考訳）: 一般確率理論に動機づけられて、$x$ in $\mathbb{r}^d$ が \emph{antipodal of rank $k$} であるとは、任意の$k+1$ の元に対して$q_1,\ldots q_{k+1}\in x$ に対して、$\mathrm{conv} x$ から $k$-dimensional simplex $\delta_k$ へのアフィン写像が存在し、$q_1,\ldots q_{k+1}$ を$k+1$ の$k+1$ の頂点に写す。 k=1$ の場合、klee が導入した(pairwise)反ポジタリティの概念と一致する。 対脚集合上のクリー問題の次の自然な一般化を考える:$\mathbb{r}^d$ におけるランク $k$ の対脚集合の最大サイズは? 我々は、ランク $k$ の対脚集合の幾何学的特徴付けを示し、元々 $k=1$ の場合のために開発された gr\"unbaum と gr\"unbaum の議論を適応させる。 この問題は、コンピュータ科学において、完全ハッシュの発見に関する古典的な問題と結びつくことができ、また、その次元においても指数的な最大サイズに対する境界が低いことを指摘した。

関連論文リスト

• 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)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。 ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
  論文  参考訳（メタデータ） (2023-10-11T22:46:09Z)
• Monogamy of entanglement between cones [68.8204255655161]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Repeated Averages on Graphs [2.363388546004777]
  我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。 また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
  論文  参考訳（メタデータ） (2022-05-09T20:18:31Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  mathbb Cd$ の正則基底の集合 $k$ は互いに非バイアスな $|langle e,frangle |2 = 1/d$ と呼ばれ、$e$ と $f$ は異なる基底の基底ベクトルである。 この対称性を(解析的に)利用して、半定値プログラムのサイズを縮小し、取り外し可能とする。
  論文  参考訳（メタデータ） (2021-11-10T14:14:53Z)
• Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal [0.7614628596146599]
  エルミート自己直交$k$-次元 truncated generalized Reed-Solomon code of length $n$ over $mathbb F_q2$ が存在することを証明する。 また、Hermitian self-orthogonal $k$-dimensional Reed-Solomon codes of length $q2+1$ over $mathbb F_q2$, for $k=q-1$ and $q$ an odd power of two.
  論文  参考訳（メタデータ） (2021-06-18T15:16:44Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• Extremal elements of a sublattice of the majorization lattice and approximate majorization [0.0]
  一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。 また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-01-23T19:09:18Z)

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

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