Fugu-MT 論文翻訳(概要): The complexity of semidefinite programs for testing $k$-block-positivity

論文の概要: The complexity of semidefinite programs for testing $k$-block-positivity

arxiv url: http://arxiv.org/abs/2601.19159v1
Date: Tue, 27 Jan 2026 03:46:06 GMT
ステータス: 翻訳完了
システム内更新日: 2026-01-28 15:26:51.161479
Title: The complexity of semidefinite programs for testing $k$-block-positivity
Title（参考訳）: k$-block-positivityをテストする半定プログラムの複雑さ
Authors: Qian Chen, Benoît Collins,
Abstract要約: 我々は$k$-block-positivity testアルゴリズムの複雑さを分析してcitechen2025srkbpを拡張する。
参考スコア（独自算出の注目度）: 4.02230249930341
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We extend \cite{chen2025srkbp} by analyzing the complexity of the $k$-block-positivity testing algorithm. In this paper, we investigate a symmetry reduction scheme based on rectangular shaped Young diagrams. Connecting the complexity to the dimensions of irreducible representations of $\mathrm{U}(d)$, we derive an explicit formula for the complexity, which also clarifies why the semidefinite program hierarchy collapses in the $k=d$ case.
Abstract（参考訳）: 我々は、$k$-block-positivity testアルゴリズムの複雑さを分析して、cite{chen2025srkbp}を拡張する。本稿では,長方形のヤング図形に基づく対称性低減手法について検討する。複雑性を$\mathrm{U}(d)$の既約表現の次元に結びつけると、複雑性の明示的な公式が導き出され、半定値のプログラム階層が$k=d$の場合で崩壊する理由も明確になる。

関連論文リスト

CSPs with Few Alien Constraints [12.330326247154968]
CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
論文参考訳（メタデータ） (2024-08-23T08:34:13Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
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)
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-07-24T04:06:11Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文参考訳（メタデータ） (2020-06-25T19:59:24Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文参考訳（メタデータ） (2020-04-16T16:12:10Z)
Complexity of Shapes Embedded in ${\mathbb Z^n}$ with a Bias Towards Squares [0.0]
形状の複雑さは、主にその相対的な性質のため、定量化が難しい品質である。複素数列が構築されたときの最も単純な形状を正方形とみなす。
論文参考訳（メタデータ） (2020-03-16T17:24:22Z)

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