Fugu-MT 論文翻訳(概要): A note about claw function with a small range

論文の概要: A note about claw function with a small range

arxiv url: http://arxiv.org/abs/2103.16390v1
Date: Tue, 30 Mar 2021 14:30:35 GMT
ステータス: 処理完了
システム内更新日: 2023-04-06 03:41:03.512636
Title: A note about claw function with a small range
Title（参考訳）: 狭い範囲の爪関数についての一考察
Authors: Andris Ambainis, Kaspars Balodis, J\=anis Iraids
Abstract要約: この問題の量子クエリの複雑さは、$Omegaleft(n1/2k1/6right)$と$Oleft(n1/2+varepsilonk1/4right)$の間である。
参考スコア（独自算出の注目度）: 1.2246649738388389
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the claw detection problem we are given two functions $f:D\rightarrow R$ and $g:D\rightarrow R$ ($|D|=n$, $|R|=k$), and we have to determine if there is exist $x,y\in D$ such that $f(x)=g(y)$. We show that the quantum query complexity of this problem is between $\Omega\left(n^{1/2}k^{1/6}\right)$ and $O\left(n^{1/2+\varepsilon}k^{1/4}\right)$ when $2\leq k<n$.
Abstract（参考訳）: 爪検出問題では、$f:D\rightarrow R$と$g:D\rightarrow R$(|D|=n$, $|R|=k$)の2つの関数が与えられ、$f が存在するかどうかを判断する必要がある。 (x)=g (y)$。この問題の量子クエリの複雑さは、$Omega\left(n^{1/2}k^{1/6}\right)$と$O\left(n^{1/2+\varepsilon}k^{1/4}\right)$の間にある。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection [0.0]
この問題の最適量子複雑性は$Omegaleft(sqrtG+(FG)1/6M1/6right)$ for input function $fcolon [F] to Z$ and $gcolon [G] to Z$であることが知られている。現在の論文は、下界が$|Z|=Omega(FG)$のすべての小さな範囲$Z$に対してさえも成り立つことを証明している。
論文参考訳（メタデータ） (2024-10-03T06:32:34Z)
Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.972653925522813]
我々は、高次H'olderの滑らかかつ一様凸関数を最小化するオラクル複雑性に対して、厳密な下界を提供する。解析は、一階および二階の滑らかさの下での関数の以前の下界を一様凸関数と同様に一般化する。
論文参考訳（メタデータ） (2024-09-16T23:17:33Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文参考訳（メタデータ） (2024-02-23T12:22:03Z)
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)
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)
Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文参考訳（メタデータ） (2021-06-25T19:14:45Z)
Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文参考訳（メタデータ） (2021-03-17T18:18:57Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

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