論文の概要: Efficiently stable presentations from error-correcting codes
- arxiv url: http://arxiv.org/abs/2311.04681v1
- Date: Wed, 8 Nov 2023 13:40:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-09 15:50:31.701896
- Title: Efficiently stable presentations from error-correcting codes
- Title（参考訳）: 誤り訂正符号からの効率的な安定な提示
- Authors: Michael Chapman, Thomas Vidick, Henry Yuen
- Abstract要約: 線形誤り訂正符号から$mathbbZk$のプレゼンテーションを構築するための一般的な方法を提案する。
結果のプレゼンテーションは、コードがエフェクト可能なときの安定性が弱いことを観察する。
このことは一般には証明できないが、量子情報理論における非局所ゲームの研究において最近の結果を活用する。
- 参考スコア（独自算出の注目度）: 5.69361786082969
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We introduce a notion of \emph{efficient stability} for finite presentations
of groups. Informally, a finite presentation using generators $S$ and relations
$R$ is \emph{stable} if any map from $S$ to unitaries that approximately
satisfies the relations (in the tracial norm) is close to the restriction of a
representation of $G$ to the subset $S$. This notion and variants thereof have
been extensively studied in recent years, in part motivated by connections to
property testing in computer science. The novelty in our work is the focus on
\emph{efficiency}, which, informally, places an onus on small presentations --
in the sense of encoding length. The goal in this setup is to achieve
non-trivial tradeoffs between the presentation length and its modulus of
stability.
With this goal in mind we analyze various natural examples of presentations.
We provide a general method for constructing presentations of $\mathbb{Z}_2^k$
from linear error-correcting codes. We observe that the resulting presentation
has a weak form of stability exactly when the code is \emph{testable}. This
raises the question of whether testable codes give rise to genuinely stable
presentations using this method. While we cannot show that this is the case in
general, we leverage recent results in the study of non-local games in quantum
information theory (Ji et al., Discrete Analysis 2021) to show that a specific
instantiation of our construction, based on the Reed-Muller family of codes,
leads to a stable presentation of $\mathbb{Z}_2^k$ of size polylog$(k)$ only.
As an application, we combine this result with recent work of de la Salle
(arXiv:2204.07084) to re-derive the quantum low-degree test of Natarajan and
Vidick (IEEE FOCS'18), which is a key building block in the recent refutation
of Connes' Embedding Problem via complexity theory (Ji et al.,
arXiv:2001.04383).
- Abstract（参考訳）: 群の有限表現に対する 'emph{efficient stability' の概念を導入する。
非公式に、ジェネレータ$s$ とリレーション$r$ を用いた有限表現が \emph{stable} であるとは、$s$ からユニタリへの(トランシアルノルムにおける)関係をほぼ満足する任意の写像が、$g$ の表現のサブセット $s$ への制限に近いことをいう。
この概念とその変種は近年広く研究され、部分的にはコンピュータ科学における財産試験とのつながりが動機となっている。
私たちの作品の新規性は、エンコード長という意味で、非公式に小さなプレゼンテーションに小音を配置する「emph{efficiency}」に焦点を当てている。
この設定の目標は、提示長さと安定性の係数の間の非自明なトレードオフを達成することである。
この目標を念頭に置いて、プレゼンテーションの自然な例を分析します。
線形誤り訂正符号から$\mathbb{Z}_2^k$のプレゼンテーションを構築するための一般的な方法を提案する。
結果の表現は、コードが \emph{testable} であるときの安定性が弱いことを観察する。
これは、テスト可能なコードが本手法を使って真に安定したプレゼンテーションをもたらすかどうかという疑問を提起する。
このことは一般には証明できないが、近年の量子情報理論における非局所ゲームの研究(Ji et al., Discrete Analysis 2021)の結果を利用して、Reed-Mullerの符号族に基づく我々の構成の特定のインスタンス化が、$\mathbb{Z}_2^k$ of size polylog$(k)$ onlyという安定した表現をもたらすことを示す。
例えば、この結果と最近のデ・ラ・サール(arxiv:2204.07084)の研究を組み合わせることで、ナタラジャンとヴィディック(ieee focs'18)の量子低次テストを再導出し、これは複雑性理論(ji et al., arxiv:2001.04383)によるコンヌの埋め込み問題に対する最近の反論において重要な構成要素である。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Tighter PAC-Bayes Bounds Through Coin-Betting [31.148069991567215]
我々は,PAC-Bayes境界の証明戦略を洗練し,より厳密な保証を実現する方法を示す。
PAC-Bayes濃度の不等式は,全ての試料サイズを同時に保持するコインベッティング法に基づいて導出する。
論文 参考訳（メタデータ） (2023-02-12T01:16:27Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳（メタデータ） (2022-05-31T17:59:09Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Classical Dynamics from Self-Consistency Equations in Quantum Mechanics
-- Extended Version [0.0]
我々は、ボナの非線形量子力学の一般化に対する新しい数学的アプローチを提案する。
自己整合性の中心的な役割を強調します。
いくつかの新しい数学的概念が紹介され、これはおそらくそれ自体が興味深い。
論文 参考訳（メタデータ） (2020-09-10T16:20:25Z) - A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
論文 参考訳（メタデータ） (2020-02-25T11:46:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。