論文の概要: m-Nearly k-Universal Words -- Investigating Simon Congruence
- arxiv url: http://arxiv.org/abs/2202.07981v1
- Date: Wed, 16 Feb 2022 10:45:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-17 15:13:35.084392
- Title: m-Nearly k-Universal Words -- Investigating Simon Congruence
- Title(参考訳): m-Nearly k-Universal Words -- Simon Congruence の調査
- Authors: Pamela Fleischmann and Lukas Haschke and Annika Huch and Annika
Mayrock and Dirk Nowotka
- Abstract要約: 2つの単語 $u$ と $v$ は、それらが同じ散乱因子の集合を持つ場合、サイモン合同 (Simon congruent) と呼ばれる。
さらに、$w$が$(k-1)$-ユニバーサルであれば、いくつかの結果が得られます。
- 参考スコア(独自算出の注目度): 1.3229510087215552
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Determining the index of the Simon congruence is a long outstanding open
problem. Two words $u$ and $v$ are called Simon congruent if they have the same
set of scattered factors, which are parts of the word in the correct order but
not necessarily consecutive, e.g., $\mathtt{oath}$ is a scattered factor of
$\mathtt{logarithm}$. Following the idea of scattered factor $k$-universality,
we investigate $m$-nearly $k$-universality, i.e., words where $m$ scattered
factors of length $k$ are absent, w.r.t. Simon congruence. We present a full
characterisation as well as the index of the congruence for $m=1$. For $m\neq
1$, we show some results if in addition $w$ is $(k-1)$-universal as well as
some further insights for different $m$.
- Abstract(参考訳): サイモン合同の指数を決定することは、長い目覚ましい開問題である。
2つの単語 $u$ と $v$ がサイモン合同(Simon congruent) (Simon congruent) と呼ばれるのは、それらが同じ散乱因子の集合を持ち、それが正しい順序で単語の一部であり、必ずしも連続ではない場合である。
分散係数 $k$-universality のアイデアに従い、$m$-nearly $k$-universality、すなわち、$m$ の散乱係数が$k$ が存在しない単語、w.r.t. simon congruence を調査した。
我々は、m=1$ の合同の指標と同様に完全な特徴付けを示す。
m\neq 1$ の場合、$w$ が $(k-1)$-universal であることに加え、異なる $m$ に対するさらなる洞察がある場合、いくつかの結果を示す。
関連論文リスト
- Dimension-free Remez Inequalities and norm designs [48.5897526636987]
ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。
ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
論文 参考訳(メタデータ) (2023-10-11T22:46:09Z) - $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence [1.5935205681539144]
1991年、H'ebrardは単語の因数分解を導入し、単語の散らばった要因を調べる強力なツールとなった。
これに基づいて、最初のカランディカールとシュネーベレンは$k$-richness(英語版)という概念を導入し、後にBarkerらに$k$-universality(英語版)という概念を導入した。
2022年、フライシュマンらは、単語のアーチ因数分解とその逆を交差させることにより、アーチ因数分解の一般化を提示した。
論文 参考訳(メタデータ) (2023-06-25T10:16:49Z) - Constructions of $k$-uniform states in heterogeneous systems [65.63939256159891]
一般の$k$に対して、異種系において$k$-一様状態を構成するための2つの一般的な方法を提案する。
我々は、各サブシステムの局所次元が素数となるような多くの新しい$k$一様状態を生成することができる。
論文 参考訳(メタデータ) (2023-05-22T06:58:16Z) - 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) - 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) - A rigidity property of complete systems of mutually unbiased bases [0.0]
我々は、ある単位ベクトル $b_1,ldots b_n$ in $mathbb Cd$ に対して、それらは$d+1$正則基底に配置できることを示した。
論文 参考訳(メタデータ) (2021-11-30T20:47:16Z) - 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) - Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
単語のバイナリ関係が与えられたとき、$tau$-Gray サイクルを有限言語 $X$ 上で定義し、置換 $left(w_[i]right)_0le ile |X|-1$ of $X$ とする。
アルファベットの基数と引数$n$のすべてのケースに対して有界な$lambda(n)$を計算する。
論文 参考訳(メタデータ) (2021-08-31T07:49:15Z) - Scattered Factor Universality -- The Power of the Remainder [1.8065361710947976]
Scattered Factor (circular) はBarkerらによって最初に導入された。
2020年。
2つの問題、すなわち、主定理の1つを任意のアルファベットに一般化し、他の定理をわずかに修正したことを証明する。
論文 参考訳(メタデータ) (2021-04-19T05:45:44Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。