論文の概要: Generalized and Unified Equivalences between Hardness and Pseudoentropy
- arxiv url: http://arxiv.org/abs/2507.05972v1
- Date: Tue, 08 Jul 2025 13:27:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-09 16:34:38.13473
- Title: Generalized and Unified Equivalences between Hardness and Pseudoentropy
- Title（参考訳）: 硬さと擬似エントロピーの一般的および統一的等価性
- Authors: Lunjia Hu, Salil Vadhan,
- Abstract要約: 計算の一様モデルと非一様モデルの両方に対して、従来の結果を一般化し、強化する統一擬似エントロピー特性を証明した。
我々の特徴づけは、シャノンエントロピーとミンエントロピーの共通概念を特別な場合として含むエントロピーの概念の一般族である。
- 参考スコア（独自算出の注目度）: 2.847905121762714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pseudoentropy characterizations provide a quantitatively precise demonstration of the close relationship between computational hardness and computational randomness. We prove a unified pseudoentropy characterization that generalizes and strengthens previous results for both uniform and non-uniform models of computation. Our characterization holds for a general family of entropy notions that encompasses the common notions of Shannon entropy and min entropy as special cases. Moreover, we show that the characterizations for different entropy notions can be simultaneously achieved by a single, universal function that simultaneously witnesses computational hardness and computational randomness. A key technical insight of our work is that the notion of weight-restricted calibration from the recent literature on algorithm fairness, along with standard computational indistinguishability (known as multiaccuracy in the fairness literature), suffices for proving pseudoentropy characterizations for general entropy notions. This demonstrates the power of weight-restricted calibration to enhance the classic Complexity-Theoretic Regularity Lemma (Trevisan, Tulsiani, and Vadhan, 2009) and Leakage Simulation Lemma (Jetchev and Pietrzak, 2014) and allows us to achieve an exponential improvement in the complexity dependency on the alphabet size compared to the pseudoentropy characterizations by Casacuberta, Dwork, and Vadhan (2024) based on the much stronger notion of multicalibration. We show that the exponential dependency on the alphabet size is inevitable for multicalibration as well as for the weaker notion of calibrated multiaccuracy.
- Abstract（参考訳）: 擬エントロピー特性は、計算硬度と計算ランダムネスの密接な関係を定量的に証明する。
計算の一様モデルと非一様モデルの両方に対して、従来の結果を一般化し、強化する統一擬似エントロピー特性を証明した。
我々の特徴づけは、シャノンエントロピーとミンエントロピーの共通概念を特別な場合として含むエントロピーの概念の一般族である。
さらに,異なるエントロピー概念のキャラクタリゼーションは,計算硬度と計算ランダム度を同時に確認する単一の普遍関数によって同時に達成可能であることを示す。
我々の研究の重要な技術的洞察は、アルゴリズムの公正性に関する最近の文献から、量制限されたキャリブレーションの概念と、一般的なエントロピーの概念の擬エントロピー的特徴を証明するのに十分である、というものである。
このことは、古典的な複雑性-理論的正則性レマ(Trevisan, Tulsiani, and Vadhan, 2009)と漏洩シミュレーションレマ(Jetchev and Pietrzak, 2014)を強化するために、量制限キャリブレーションの力を示し、より強いマルチキャリブレーションの概念に基づくCasacuberta, Dwork, Vadhan(2024)の擬エントロピー特性と比較して、アルファベットサイズに対する複雑性依存性を指数的に改善することができる。
アルファベットサイズへの指数的依存は多重校正だけでなく、校正多重精度の弱い概念にも必然的であることを示す。
関連論文リスト
- Uniform Additivity of Tripartite Optimized Correlation Measures [6.624754673303328]
正規化バージョンが計算可能である量子状態の最適化線形エントロピー関数を探索する。
我々はフォン・ノイマンエントロピーの強い部分付加性に頼って、以前に確立された3つの三部式最適化相関測度が加法であることを証明している。
論文 参考訳（メタデータ） (2024-12-24T18:28:29Z) - Efficient Pseudomode Representation and Complexity of Quantum Impurity Models [0.7373617024876725]
平衡外フェルミオン量子不純物モデル(英語版)(QIM)は、連続するフェルミオン浴に結合された小さな相互作用系を記述する。
複雑な指数関数の和によって機能する浴槽のファインマン・ヴァーノン効果の核を近似する効率の良い浴槽表現を見いだす。
本研究の成果をQIMに関連付けるため, 複合不純物-擬態系の時間進化を記述した明示的なLiouvillianを導出した。
論文 参考訳（メタデータ） (2024-09-13T13:31:53Z) - Scaling and renormalization in high-dimensional regression [72.59731158970894]
リッジ回帰に関する最近の結果について統一的な視点を提示する。
我々は、物理とディープラーニングの背景を持つ読者を対象に、ランダム行列理論と自由確率の基本的なツールを使用する。
我々の結果は拡張され、初期のスケーリング法則のモデルについて統一的な視点を提供する。
論文 参考訳（メタデータ） (2024-05-01T15:59:00Z) - Conditional Independence of 1D Gibbs States with Applications to Efficient Learning [0.0]
熱平衡におけるスピン鎖は, 個々の領域が近傍に強く相関する相関構造を持つことを示す。
これらの測度が任意の正の温度で超指数的に崩壊することを証明している。
論文 参考訳（メタデータ） (2024-02-28T17:28:01Z) - Complexity in two-point measurement schemes [0.0]
摂動を伴う2点計測プロトコルにおける可観測値の変化に伴う確率分布は,自動相関関数として記述できることを示す。
発展状態が対応する共役空間にどのように広がるのかを考察する。
プレクエンチハミルトニアンがカオスである場合にのみ、パラメータの大きい値に対して複雑性が飽和することを示す。
論文 参考訳（メタデータ） (2023-11-14T04:00:31Z) - Statistical Properties of the Entropy from Ordinal Patterns [55.551675080361335]
大規模な時系列モデルに対するエントロピー・統計複雑性の連立分布を知っていれば、今日まで利用できない統計テストが可能になるだろう。
実正規化エントロピーが零でも1でもないモデルに対して、経験的シャノンのエントロピーの分布を特徴づける。
2つの信号が同じシャノンのエントロピーを持つ順序パターンを生成するという仮説を否定するのに十分な証拠があるかどうかを検証する。
論文 参考訳（メタデータ） (2022-09-15T23:55:58Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - The variance of relative surprisal as single-shot quantifier [0.0]
我々は、(相対的な)前提条件が、単発設定における量子状態のペア間の近似状態遷移に十分な条件を与えることを示す。
さらに、(相対的な)エントロピーの、単純で物理的に魅力的な単一ショットのキャラクタリゼーションを導出する。
論文 参考訳（メタデータ） (2020-09-17T16:06:54Z) - Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
経験的最適化は現代の機械学習の中心であるが、その成功における役割はまだ不明である。
分散による離散乗法雑音のパラメータによく現れることを示す。
最新のステップサイズやデータを含む重要な要素について、詳細な分析を行い、いずれも最先端のニューラルネットワークモデルで同様の結果を示す。
論文 参考訳（メタデータ） (2020-06-11T09:58:01Z) - Profile Entropy: A Fundamental Measure for the Learnability and
Compressibility of Discrete Distributions [63.60499266361255]
離散分布のサンプルに対して、プロファイルエントロピーは推定、推論、圧縮の概念を統一する基本的な尺度であることを示す。
具体的には、プロファイルエントロピー a) は、最適自然推定器に対する分布を推定する速度を決定する; b) 任意のラベル不変分布コレクションに対する最適推定器と比較して全ての対称特性を推定する速度を特徴付ける; c) プロファイル圧縮の限界として機能する。
論文 参考訳（メタデータ） (2020-02-26T17:49:04Z) - Fast approximations in the homogeneous Ising model for use in scene
analysis [61.0951285821105]
我々は、推論に必要な量を数値計算できる正確な近似を提供する。
近似式はスケーラブルでマルコフランダム場の大きさに満足できないことを示す。
機能的磁気共鳴イメージングアクティベーション検出実験においてベイズ推論を行い, ピスタチオ樹収量の年次増加の空間パターンにおける異方性に対する確率比試験を行った。
論文 参考訳（メタデータ） (2017-12-06T14:24:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。