Fugu-MT 論文翻訳(概要): On combinatorial structures in linear codes

論文の概要: On combinatorial structures in linear codes

arxiv url: http://arxiv.org/abs/2309.16411v1
Date: Thu, 28 Sep 2023 13:03:41 GMT
ステータス: 処理完了
システム内更新日: 2023-09-29 14:26:48.529915
Title: On combinatorial structures in linear codes
Title（参考訳）: 線形符号の組合せ構造について
Authors: Nou\'edyn Baspin
Abstract要約: K_i$sが$tildeOmegaleft(k/nright)$-expanderであることを示す。特に、古典符号の BPT はすべてのユークリッド次元において厳密であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work we show that given a connectivity graph $G$ of a $[[n,k,d]]$ quantum code, there exists $\{K_i\}_i, K_i \subset G$, such that $\sum_i |K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, and the $K_i$'s are $\tilde{\Omega}( \sqrt{{k}/{n}})$-expander. If the codes are classical we show instead that the $K_i$'s are $\tilde{\Omega}\left({{k}/{n}}\right)$-expander. We also show converses to these bounds. In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions. Finally, we prove structural theorems for graphs with no "dense" subgraphs which might be of independent interest.
Abstract（参考訳）: この研究において、$[n,k,d] の接続グラフ $G$ が与えられたとき、$\sum_i |K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, $K_i$'s が$\tilde{\Omega}( \sqrt{k}/{n}})$-expander となるような$\{K_i\}_i, K_i \subset G$ が存在する。もしコードがクラシックなら、代わりに$k_i$'sが$\tilde{\omega}\left({{k}/{n}}\right)$-expanderであることを示します。また、これらの境界に対する逆も示す。特に、古典符号の BPT はすべてのユークリッド次元において厳密であることを示す。最後に、独立した関心を持つような「くだらない」部分グラフを持たないグラフの構造定理を証明する。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文参考訳（メタデータ） (2024-02-23T12:22:03Z)
An advance in the arithmetic of the Lie groups as an alternative to the forms of the Campbell-Baker-Hausdorff-Dynkin theorem [0.7373617024876725]
作用素や行列の指数は量子論において広く用いられるが、評価するのは難しいこともある。ここで、$rm eabf X+bbf Y$ が $rm epbf Zrm eqbf Xrm e-pbf Z$ for scalar $p$ および $q$ と同値であることが証明されている。
論文参考訳（メタデータ） (2024-01-28T19:20:02Z)
Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文参考訳（メタデータ） (2023-11-13T00:45:41Z)
Embedding Inequalities for Barron-type Spaces [4.184052796218818]
定数は入力次元$d$に依存しないことを示し、埋め込みが高次元で有効であることを示唆する。また、下界と上界の両方がきつくなっていることも示している。
論文参考訳（メタデータ） (2023-05-30T14:45:51Z)
Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions [6.164223149261533]
V=phi_i: mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd to mathbbRd
論文参考訳（メタデータ） (2023-05-20T14:50:34Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
$mathcalM$ を $mathbbRN$ のコンパクト $d$-次元部分多様体とし、リーチ $tau$ とボリューム $V_mathcal M$ とする。非線形関数 $f: mathbbRN rightarrow mathbbRmm が存在し、$m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math が存在することを証明します。
論文参考訳（メタデータ） (2022-06-07T15:10:46Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文参考訳（メタデータ） (2021-03-10T07:33:03Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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