論文の概要: 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つの比較のコストを超えることはなく、場合によってはそれよりも低い場合もあります。
関連論文リスト
- The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - Almost-Optimal Computational Basis State Transpositions [3.266650216648532]
我々は$Theta(n)$ gatesを使って任意の$n$-qubitの計算基底状態変換を行う。
これは、最悪のケースと平均ケースゲートの複雑さにおいて、より低い境界$Omega(n/log(nd))$とほぼ一致する。
論文 参考訳(メタデータ) (2023-09-22T12:19:59Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳(メタデータ) (2023-02-20T19:11:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。