論文の概要: Complexity and Avoidance
- arxiv url: http://arxiv.org/abs/2204.11289v1
- Date: Sun, 24 Apr 2022 14:36:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-27 01:02:37.560251
- Title: Complexity and Avoidance
- Title(参考訳): 複雑さと回避
- Authors: Hayden Jananthan
- Abstract要約: 適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。
シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this dissertation we examine the relationships between the several
hierarchies, including the complexity, $\mathrm{LUA}$ (Linearly Universal
Avoidance), and shift complexity hierarchies, with an eye towards quantitative
bounds on growth rates therein. We show that for suitable $f$ and $p$, there
are $q$ and $g$ such that $\mathrm{LUA}(q) \leq_\mathrm{s} \mathrm{COMPLEX}(f)$
and $\mathrm{COMPLEX}(g) \leq_\mathrm{s} \mathrm{LUA}(p)$, as well as quantify
the growth rates of $q$ and $g$. In the opposite direction, we show that for
certain sub-identical $f$ satisfying $\lim_{n \to \infty}{f(n)/n}=1$ there is a
$q$ such that $\mathrm{COMPLEX}(f) \leq_\mathrm{w} \mathrm{LUA}(q)$, and for
certain fast-growing $p$ there is a $g$ such that $\mathrm{LUA}(p)
\leq_\mathrm{s} \mathrm{COMPLEX}(g)$, as well as quantify the growth rates of
$q$ and $g$.
Concerning shift complexity, explicit bounds are given on how slow-growing
$q$ must be for any member of $\rm{LUA}(q)$ to compute $\delta$-shift complex
sequences. Motivated by the complexity hierarchy, we generalize the notion of
shift complexity to consider sequences $X$ satisfying $\operatorname{KP}(\tau)
\geq f(|\tau|) - O(1)$ for all substrings $\tau$ of $X$ where $f$ is any order
function. We show that for sufficiently slow-growing $f$, $f$-shift complex
sequences can be uniformly computed by $g$-complex sequences, where $g$ grows
slightly faster than $f$.
The structure of the $\mathrm{LUA}$ hierarchy is examined using bushy tree
forcing, with the main result being that for any order function $p$, there is a
slow-growing order function $q$ such that $\mathrm{LUA}(p)$ and
$\mathrm{LUA}(q)$ are weakly incomparable. Using this, we prove new results
about the filter of the weak degrees of deep nonempty $\Pi^0_1$ classes and the
connection between the shift complexity and $\mathrm{LUA}$ hierarchies.
- Abstract(参考訳): この論文では、複雑性、$\mathrm{LUA}$(Linearly Universal Avoidance)およびシフト複雑性階層を含むいくつかの階層間の関係を、成長速度の定量的な境界に注目して検討する。
適切な$f$と$p$に対して、$q$と$g$があり、$\mathrm{LUA} であることを示す。
(q) \leq_\mathrm{s} \mathrm{COMPLEX}
(f)$ と $\mathrm{complex}
(g) \leq_\mathrm{s} \mathrm{LUA}
(p)$および$q$および$g$の成長率の定量化。
逆向きに、$\lim_{n \to \infty}{f(n)/n}=1$を満たす部分同一の$f$ に対して$\mathrm{complex} となる$q$ が存在することを示す。
(f) \leq_\mathrm{w} \mathrm{LUA}
(q)$と、ある急速に成長する$p$に対して、$\mathrm{LUA} となる$g$が存在する。
(p) \leq_\mathrm{s} \mathrm{COMPLEX}
(g)$および$q$および$g$の成長率の定量化。
シフト複雑性に関して、$\rm{LUA} の任意のメンバに対して、q$ がどれだけ遅く成長するかを明確に制限する。
(q)$ で$\delta$-shift の複素列を計算する。
複雑性階層に動機付けられ、シフト複雑性の概念を一般化して、$X$ を満たす列 $\operatorname{KP}(\tau) \geq f(|\tau|) - O(1)$ をすべての部分弦に対して $\tau$ of $X$ とする。
十分にゆっくり成長する$f$の場合、$f$-shift複素列は$g$-complex sequencesによって一様に計算され、$g$は$f$よりもわずかに速く成長する。
$\mathrm{LUA}$階層の構造は、ブッディーツリーの強制によって調べられ、主な結果は、任意の順序関数$p$に対して、$\mathrm{LUA} のようなゆっくりと成長する順序関数 $q$ が存在することである。
(p)$ と $\mathrm{lua}
(q)$は弱可算である。
これを用いて、深い空でない$\Pi^0_1$クラスの弱度フィルタとシフト複雑性と$\mathrm{LUA}$階層との間の接続に関する新しい結果を示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳(メタデータ) (2024-08-22T17:57:58Z) - $\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) - Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。
我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
論文 参考訳(メタデータ) (2023-01-01T08:30:35Z) - Randomised Composition and Small-Bias Minimax [0.9252523881586053]
クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。
まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
論文 参考訳(メタデータ) (2022-08-26T23:32:19Z) - 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 a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - 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 Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。