Fugu-MT 論文翻訳(概要): Marton's conjecture in polynomial time

論文の概要: Marton's conjecture in polynomial time

arxiv url: http://arxiv.org/abs/2609.20771v1
Date: Thu, 17 Sep 2026 17:46:43 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-20 08:55:54.411151
Title: Marton's conjecture in polynomial time
Title（参考訳）: 多項式時間におけるマートンの予想
Abstract要約: マートンのフライマン・ルッツァ予想にアルゴリズム的対応を与える。応用として、様々な学習問題に対する非依存時間アルゴリズムを得る。
参考スコア（独自算出の注目度）: 2.986556069071589
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose $K^{O(1)}$ translates cover $A$. The algorithm runs in $\textsf{poly}(n,K)$ time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich-Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.
Abstract（参考訳）: Gowers, Green, Manners, and Tao (Annals '25) は、最近、マートンの多項式 Freiman-Ruzsa 予想を解いた。 A \subseteq \mathbb{F}_2^n$ の集合に対する一様サンプリングとメンバシップ-オークルアクセスが与えられたとき、このアルゴリズムは最大で 2 倍定数の $K$ に対して、最大で $|A|$ のサイズの部分空間を出力し、その$K^{O(1)}$ はカバー$A$ を変換する。このアルゴリズムは$\textsf{poly}(n,K)$ timeで動作する。応用として、Goldreich-Levin2次学習問題に対する多項式時間アルゴリズム、安定化状態の不適切な非依存トモグラフィー、有界安定化状態範囲の量子状態のトモグラフィーなど、様々な学習問題に対する多項式時間アルゴリズムを得る。

関連論文リスト

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文参考訳（メタデータ） (2026-09-09T10:13:43Z)
Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields [1.4323566945483497]
有限体上のローレントルムの解数の近似について検討する。我々の最初の主要な結果は、成功確率1-$で、$widehat(f)$ fulfilling [ |widehatN(f) - N(f)| le varepsilon qn+s/2-]を出力する量子アルゴリズムである。 2つ目の主要な結果として、ランダム時間チューリング還元の下で同じ問題が$#$P-hardになることを示す。
論文参考訳（メタデータ） (2026-08-25T00:23:27Z)
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications [13.39372872460586]
mathbbRn times d$ の行列 $X の 2 つの右幅 q$ノルムは $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$ と定義される。 FOCS(Exponential Time hypothesis)を仮定すると、単純なスペクトルアルゴリズムは2sqrtlog n$よりも近似係数がよいことを示す。
論文参考訳（メタデータ） (2026-05-24T23:56:06Z)
Quantum Advantage via Solving Multivariate Polynomials [21.099298465042583]
3次関数はランダムなオラクルをインスタンス化して非相対化量子優位を得るのに十分であることを示す。 p_i(x_ldots,x_n)=y_i_iin [m]$ for $mn$ over $mathbbF$。
論文参考訳（メタデータ） (2025-09-08T23:19:20Z)
A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
変分不等式(SVIs)の解決は、最適化の中心にある基礎的な問題である。ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに重点を置いている。
論文参考訳（メタデータ） (2025-04-04T13:24:41Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文参考訳（メタデータ） (2022-03-24T08:14:12Z)
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)
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
論文参考訳（メタデータ） (2022-03-05T17:25:37Z)
Private and polynomial time algorithms for learning Gaussians and beyond [13.947461378608525]
本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
論文参考訳（メタデータ） (2021-11-22T16:25:51Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)

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