Fugu-MT 論文翻訳(概要): The multiplicative complexity of interval checking

論文の概要: The multiplicative complexity of interval checking

arxiv url: http://arxiv.org/abs/2201.10200v1
Date: Tue, 25 Jan 2022 09:30:18 GMT
ステータス: 処理完了
システム内更新日: 2023-02-27 22:48:44.939120
Title: The multiplicative complexity of interval checking
Title（参考訳）: 区間検査の乗法的複雑性
Authors: Thomas H\"aner and Mathias Soeken
Abstract要約: a$ と $b$ が定数整数である場合、$aleq x b$ のチェックの正確な AND-gate コストを決定する。おそらく驚くべきことに、インターバルチェックのコストが1つの比較のコストを超えることはない。
参考スコア（独自算出の注目度）: 1.4902915966744057
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.
Abstract（参考訳）: ここで、$a$ と $b$ が定数整数である場合、$a\leq x < b$ をチェックする正確なゲートとゲートのコストを決定する。おそらく意外なことに、インターバルチェックのコストが1つの比較のコストを超えることはなく、場合によってはそれよりも低い場合もあります。

関連論文リスト

Quantum Algorithm for the Multiple String Matching Problem [0.0]
我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-22T10:50:43Z)
Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
論文参考訳（メタデータ） (2024-10-09T12:05:26Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
本稿では,2つのパリンドロムを結合した文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-17T07:19:20Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文参考訳（メタデータ） (2021-11-09T16:50:18Z)
Simplest non-additive measures of quantum resources [77.34726150561087]
我々は $cal E(rhootimes N) = E(e;N) ne Ne$ で説明できる測度について研究する。
論文参考訳（メタデータ） (2021-06-23T20:27:04Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
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)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)
Learning bounded subsets of $L_p$ [8.147652597876862]
基礎となるクラスが$L_p$の有界部分集合であり、対象の$Y$が$L_p$に属する学習問題を研究する。任意の$p > 4$ の急激なサンプル複雑性の推定値を示す。
論文参考訳（メタデータ） (2020-02-04T09:25:34Z)

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