論文の概要: Two Linear Programs are Better than One

• arxiv url: http://arxiv.org/abs/2610.15909v1
• Date: Sun, 11 Oct 2026 20:44:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-19 15:21:43.971966
• Title: Two Linear Programs are Better than One
• Title（参考訳）: 2つの線形プログラムは1より優れている
• Abstract要約: 拡張複雑性 $operatornamexc(P)$ of a polytope $P$ は、ポリトープに投影されるポリトープの最小の面数である。 ニューラルネットワークの複雑さに触発されたHertrichとLohoは、ポリトープ$P$の仮想拡張複雑性$operatornamevxc(P)$を導入した。
• 参考スコア（独自算出の注目度）: 46.125603835411376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.
• Abstract（参考訳）: 拡張複雑性 $\operatorname{xc}(P)$ of a polytope $P$ は、ポリトープに投影されるポリトープの最小のファセット数である。 ニューラルネットワークの複雑さにより、Hertrich と Loho は仮想拡張複雑性 $\operatorname{vxc}(P)$ of a polytope $P$, is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ of all polytopes $Q$ and $R$ such as $P+Q=R$。 仮想拡張複雑性に関する以下の結果を示す。 まず、仮想拡張複雑性が拡張複雑性よりも指数関数的に小さいことを示すことにより、このトピックのコアオープンな問題を解決する。 第2に、Hrubeš による半代数的数え上げ引数を適用し、ロスボスの数え上げ引数を拡張することにより、指数関数的仮想拡張複雑性を持つマトロイド基底ポリトープが存在することを示す。 最後に、$n$頂点を持つポリゴンの最大仮想拡張複雑性は、$(\sqrt{n})$であることを示す。 これは、仮想拡張複雑性の場合の2011年のフィオリーニ、ロスヴォス、ティワリーの拡張複雑性に関する質問の類似を解決している。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Neural Networks and (Virtual) Extended Formulations [8.185918509343818]
  私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。 我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
  論文  参考訳（メタデータ） (2024-11-05T11:12:11Z)
• 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)
• Complexity and Avoidance [0.0]
  適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。 シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
  論文  参考訳（メタデータ） (2022-04-24T14:36:38Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。