論文の概要: 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$ に対するさらなる洞察がある場合、いくつかの結果を示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - 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) - 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) - 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) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。