Fugu-MT 論文翻訳(概要): On the $k$-Hamming and $k$-Edit Distances

論文の概要: On the $k$-Hamming and $k$-Edit Distances

arxiv url: http://arxiv.org/abs/2306.09144v1
Date: Thu, 15 Jun 2023 14:03:28 GMT
ステータス: 処理完了
システム内更新日: 2023-06-16 14:23:53.333962
Title: On the $k$-Hamming and $k$-Edit Distances
Title（参考訳）: $k$-Hamming と $k$-Edit 距離について
Authors: Chiara Epifanio and Luca Forlizzi and Francesca Marzi and Filippo Mignosi and Giuseppe Placidi and Matteo Spezialetti
Abstract要約: 我々は、古典的なハミングと編集距離の自然な一般化である、重量付き$k$ハミングと$k$-Edit距離を考える。
参考スコア（独自算出の注目度）: 1.5821816117324743
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we consider the weighted $k$-Hamming and $k$-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any $k\geq 2$ the DECIS-$k$-Hamming problem is $\mathbb{P}$-SPACE-complete and the DECIS-$k$-Edit problem is NEXPTIME-complete.
Abstract（参考訳）: 本稿では、古典的なハミングと編集距離の自然な一般化である、重量付き$k$ハミングと$k$-Edit距離について考察する。この論文の主な結果として、任意の$k\geq 2$ the DECIS-$k$-Hamming 問題は $\mathbb{P}$-SPACE-complete であり、DECIS-$k$-Edit 問題は NEXPTIME-complete であることを示す。

関連論文リスト

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)
$\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)
Time Evolution of Typical Pure States from a Macroscopic Hilbert Subspace [0.0]
我々は、純状態$psi_tin MathcalH$を単位的に進化させたマクロ量子系を考える。重ね合わせ重みの進化に関する2つの事実を証明し、|P_nupsi_t|2$とする。
論文参考訳（メタデータ） (2022-10-18T17:37:42Z)
Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文参考訳（メタデータ） (2022-07-28T17:50:53Z)
Feasibility and method of multi-step Hermitization of crypto-Hermitian quantum Hamiltonians [0.0]
非エルミート的ハミルトニアン(すなわち、$H neq Hdagger$)をヘルミート可能とするユニタリモデルを構築する。ハミルトニアン $H = Hddagger$ の必要ハーミシティは、内積に対する単なる計量による修正 $langle psi_a|psi_brangle$ によって達成できる。
論文参考訳（メタデータ） (2022-03-05T07:24:51Z)
Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文参考訳（メタデータ） (2021-06-25T17:03:38Z)
Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal [0.7614628596146599]
エルミート自己直交$k$-次元 truncated generalized Reed-Solomon code of length $n$ over $mathbb F_q2$ が存在することを証明する。また、Hermitian self-orthogonal $k$-dimensional Reed-Solomon codes of length $q2+1$ over $mathbb F_q2$, for $k=q-1$ and $q$ an odd power of two.
論文参考訳（メタデータ） (2021-06-18T15:16: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 self-adjointness of H+A*+A [0.0]
我々は、形式的ハミルトニアン$H+A*+A$と$D(hat H)cap D(hat H)=0$との自己随伴実現を$hat H$で構築する。我々は、$hat H$ を、種数 $H+A*_n+A_n+E_n$ の列の(ノルムの)極限として記述する問題を考える。
論文参考訳（メタデータ） (2020-03-11T16:57:52Z)
Completing the quantum formalism in a contextually objective framework [0.0]
標準的な量子力学では、状態ベクトル $| psi ラングル$ は無限に多くの異なる直交基底に属する。理想化された場合、$A$を何度も測定すると、同じ固有値で同じ結果が繰り返される。なぜなら、$| psi rangle$は、$mu$を取得できる完全なオブザーバブルな$A$を指定していないからである。
論文参考訳（メタデータ） (2020-03-06T10:27:10Z)

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