論文の概要: Approximate Counting in Local Lemma Regimes

• arxiv url: http://arxiv.org/abs/2512.10134v1
• Date: Wed, 10 Dec 2025 22:26:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-12 16:15:42.097392
• Title: Approximate Counting in Local Lemma Regimes
• Title（参考訳）: 局所レムマレジームにおける近似数
• Authors: Ryan L. Mann, Gabriel Waite,
• Abstract要約: 事象の交叉確率と部分空間の交叉次元を考える。 一般のプロジェクタに対しては,グローバル包摂安定性条件下での完全時間近似スキームと,スペクトルギャップ仮定下での効率的なアフィン近似の2つのアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish efficient approximate counting algorithms for several natural problems in local lemma regimes. In particular, we consider the probability of intersection of events and the dimension of intersection of subspaces. Our approach is based on the cluster expansion method. We obtain fully polynomial-time approximation schemes for both the probability of intersection and the dimension of intersection for commuting projectors. For general projectors, we provide two algorithms: a fully polynomial-time approximation scheme under a global inclusion-exclusion stability condition, and an efficient affine approximation under a spectral gap assumption. As corollaries of our results, we obtain efficient algorithms for approximating the number of satisfying assignments of conjunctive normal form formulae and the dimension of satisfying subspaces of quantum satisfiability formulae.
• Abstract（参考訳）: 局所補題制度におけるいくつかの自然問題に対する効率的な近似的数え上げアルゴリズムを確立する。 特に、事象の交叉確率と部分空間の交叉次元を考える。 本手法はクラスタ展開法に基づく。 我々は、可換プロジェクタの交叉確率と交叉次元の両方に対する多項式時間近似スキームを得る。 一般のプロジェクタに対しては、大域包含-排他安定条件下での完全多項式時間近似スキームと、スペクトルギャップ仮定下での効率的なアフィン近似の2つのアルゴリズムを提供する。 その結果, 共役正規形式公式の充足数と量子充足可能性公式の充足部分空間を充足する次元を近似する効率的なアルゴリズムが得られた。

関連論文リスト

• Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Models [0.5156484100374059]
  我々は、PLetrized line search に基づくアプローチと、一般的な検索方向を用いたアプローチに焦点をあてる。 我々は、アルゴリズムの一般クラスの高速収束を証明するために必要となる方向のさらなる性質について光を当てた。 運動量、共役勾配、適応的事前条件法に線探索を統合することが興味があるかもしれない。
  論文  参考訳（メタデータ） (2024-08-06T13:58:37Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Orthogonal Polynomials Approximation Algorithm (OPAA):a functional analytic approach to estimating probability densities [0.0]
  新しい直交多項式近似アルゴリズム(OPAA)を提案する。 OPAAは機能解析手法を用いて確率分布を推定する。 後部の正規化重量を推定するために応用できる。
  論文  参考訳（メタデータ） (2022-11-16T00:51:00Z)
• Amplitude Amplification for Optimization via Subdivided Phase Oracle [0.9176056742068814]
  振幅増幅の修正版を用いて最適化問題を解くアルゴリズムを提案する。 数値シミュレーションにより, 対象値の正規分布, 歪正規分布, 指数分布分布に対して, 最適解の確率を増幅するアルゴリズムが有効であることを示す。
  論文  参考訳（メタデータ） (2022-05-02T01:14:27Z)

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

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