論文の概要: 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)$ を計算する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - $\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) - Realization of an arbitrary structure of perfect distinguishability of
states in general probability theory [0.0]
単一の要素を持つすべてのサブセットは、もちろん$mathcal A$であり、より小さなコレクションは、$Hin Mathcal A$ と $L subset H$ then $Lin mathcal A$; 言い換えれば、$mathcal A$ は $textitindependence system$ と呼ばれる、インデックスの集合上の $[n]$ である。
論文 参考訳（メタデータ） (2023-01-16T18:33: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。