論文の概要: Gray Cycles of Maximum Length Related to k-Character Substitutions
- arxiv url: http://arxiv.org/abs/2108.13659v1
- Date: Tue, 31 Aug 2021 07:49:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-01 14:28:00.549265
- Title: Gray Cycles of Maximum Length Related to k-Character Substitutions
- Title(参考訳): k-キャラクタ置換に関する最大長さのグレーサイクル
- Authors: Jean N\'eraud (LITIS, UNIROUEN)
- Abstract要約: 単語のバイナリ関係が与えられたとき、$tau$-Gray サイクルを有限言語 $X$ 上で定義し、置換 $left(w_[i]right)_0le ile |X|-1$ of $X$ とする。
アルファベットの基数と引数$n$のすべてのケースに対して有界な$lambda(n)$を計算する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a word binary relation $\tau$ we define a $\tau$-Gray cycle over a
finite language $X$ to be a permutation $\left(w_{[i]}\right)_{0\le i\le
|X|-1}$ of $X$ such that each word $w_i$ is an image of the previous word
$w_{i-1}$ by $\tau$. In that framework, we introduce the complexity measure
$\lambda(n)$, equal to the largest cardinality of a language $X$ having words
of length at most $n$, and such that a $\tau$-Gray cycle over $X$ exists. The
present paper is concerned with the relation $\tau=\sigma_k$, the so-called
$k$-character substitution, where $(u,v)$ belongs to $\sigma_k$ if, and only
if, the Hamming distance of $u$ and $v$ is $k$. We compute the bound
$\lambda(n)$ for all cases of the alphabet cardinality and the argument $n$.
- Abstract(参考訳): 単語のバイナリ関係 $\tau$ が与えられると、有限言語上の$x$ を$\left(w_{[i]}\right)_{0\le i\le |x|-1}$ と定義し、各単語 $w_i$ が前の単語 $w_{i-1}$ のイメージであるような$x$ を$\tau$ で定義する。
このフレームワークでは、$\lambda(n)$という、長さの単語が最大$n$である言語で最大濃度の$X$に等しい複雑性測度を導入し、$X$を超える$\tau$-Grayサイクルが存在するようにします。
本論文は、$(u,v)$が$\sigma_k$に属するようないわゆる$k$-character substitutionである$\tau=\sigma_k$の関係と、そのハミング距離が$u$と$v$が$k$であることに関係している。
アルファベットの基数と引数 $n$ のすべての場合の有界$\lambda(n)$ を計算する。
関連論文リスト
- Completely Bounded Norms of $k$-positive Maps [41.78224056793453]
演算子システム $cl S$ が与えられた場合、パラメータ $r_k(cl S)$ (resp. $d_k(cl S)$) を定義する。
シーケンス $(r_k(cl S))$ が 1$ であることと、$cl S$ が完全であることと、シーケンス $(d_k(cl S))$ が 1$ であることと、$cl S$ がリフト特性を持つことのみであることを示す。
論文 参考訳(メタデータ) (2024-01-22T20:37:14Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - 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) - When Variable-Length Codes Meet the Field of Error Detection [0.0]
citeJK97,N21の精神では、可変長符号の誤り検出補正能力は$tau_d,k$以上の条件で表現できる。
所定の正規コードに対して、それらの条件が決定可能であるかどうかを検討する。
論文 参考訳(メタデータ) (2022-08-31T08:14:28Z) - 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) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文 参考訳(メタデータ) (2022-02-03T03:45:45Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳(メタデータ) (2022-01-24T17:33:19Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳(メタデータ) (2021-09-21T13:19:04Z) - A Note on Rough Set Algebra and Core Regular Double Stone Algebras [0.0]
主定理では、$R_theta$ with $|theta_u| > 1 forall u in U$ to isomorphic to $TP_E$ and $C_3E$, and the three CRDSA's are complete and atomic。
Main Corollaryでは、$R_theta$を$TP_U$、$C_3U$、$phicirc alpha_r:R_thetahookrightに埋め込む方法を明確に示しています。
論文 参考訳(メタデータ) (2021-01-07T00:32:03Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳(メタデータ) (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。