論文の概要: Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory

• arxiv url: http://arxiv.org/abs/2509.18057v4
• Date: Mon, 06 Oct 2025 17:09:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 19:16:49.445844
• Title: Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory
• Title（参考訳）: 組合せ構造の強化生成:複雑性理論への応用
• Authors: Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta,
• Abstract要約: 効率的なアルゴリズムの既知の限界を改善する新しい構造を見つけるのにAIのテクニックが役立つかどうかを探索する。 具体的には、AlphaEvolveを使って、a)MAX-CUTの平均ケース硬度とMAX-Independent Setの2つの設定を研究します。 改良された下界は、最大163$のノード上にほぼ極端ラマヌジャングラフを構築することで得られる。
• 参考スコア（独自算出の注目度）: 3.359365297148466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We explore whether techniques from AI can help discover new combinatorial structures that improve on known limits on efficient algorithms. Specifically, we use AlphaEvolve (an LLM coding agent) to study two settings: a) Average-case hardness for MAX-CUT and MAX-Independent Set: We improve a recent result of Kunisky and Yu to obtain near-optimal upper and (conditional) lower bounds on certification algorithms for MAX-CUT and MAX-Independent Set on random 3- and 4-regular graphs. Our improved lower bounds are obtained by constructing nearly extremal Ramanujan graphs on as many as $163$ nodes, using AlphaEvolve. Additionally, via analytical arguments we strengthen the upper bounds to settle the computational hardness of these questions up to an error in the third decimal place. b) Worst-case Hardness of Approximation for MAX-k-CUT: We obtain new inapproximability results, proving that it is NP-hard to approximate MAX-4-CUT and MAX-3-CUT within factors of $0.987$ and $0.9649$ respectively, using AlphaEvolve to discover new gadget reductions. Our MAX-4-CUT result improves upon the SOTA of $0.9883$, and our MAX-3-CUT result improves on the current best gadget-based inapproximability result of $0.9853$, but falls short of improving the SOTA of $16/17$ that relies on a custom PCP, rather than a gadget reduction from "standard" H{\aa}stad-style PCPs. A key technical challenge we faced: verifying a candidate construction produced by AlphaEvolve is costly (often requiring exponential time). In both settings above, our results were enabled by using AlphaEvolve itself to evolve the verification procedure to be faster (sometimes by $10,000\times$). We conclude with a discussion of norms by which to assess the assistance from AI in developing proofs.
• Abstract（参考訳）: 我々は、AIのテクニックが、効率的なアルゴリズムの既知の限界を改善する新しい組合せ構造を発見するのに役立つかどうかを探求する。 具体的には、AlphaEvolve(LLM符号化エージェント)を使って2つの設定を研究します。 a) MAX-CUT と MAX-非依存集合に対する平均ケース硬度: ランダム 3 と 4 の正則グラフ上の MAX-CUT および MAX-非依存集合の証明アルゴリズムのほぼ最適上および(条件)下限を得るために、国スキーとユの最近の結果を改善する。 改良された下界は、AlphaEvolveを用いて最大163$のノード上に、ほぼ極端ラマヌジャングラフを構築して得られる。 さらに、解析的議論を通じて上界を強化し、これらの質問の計算硬度を3番目の十進点の誤差まで解決する。 b) MAX-k-CUT の近似の最悪のハードネス: 新しい不適応性結果を得るため、AlphaEvolve を用いて MAX-4-CUT と MAX-3-CUT を 0.987$ と $0.9649$ の係数で近似することがNPハードであることが証明された。 MAX-4-CUTの結果は0.9883ドルのSOTAで改善され、MAX-3-CUTの結果は0.9853ドルのガジェットベースの不適合性は改善されましたが、標準のH{\aa}stadスタイルのPCPからガジェットの削減ではなく、カスタムPCPに依存する16/17ドルのSOTAでは改善されませんでした。 AlphaEvolveが生成する候補構築の検証にはコストがかかる(しばしば指数時間を必要とする)。 上記の両方の設定では、AlphaEvolve自体を使用して検証手順を高速に(時には10,000\times$で)進化させました。 我々は、証明を開発する上でAIからの援助を評価するための規範に関する議論を締めくくった。

関連論文リスト

• Learning-Augmented Algorithms for Boolean Satisfiability [7.642039348547126]
  古典的ブール満足度(SAT)決定と最適化問題を2種類のアドバイスを用いて検討する。 Subsetアドバイスは最適な代入から変数のランダムな$epsilon$区切りを提供するが、ラベルアドバイス”は最適な代入ですべての変数に対してノイズの多い予測を提供する。 最適化問題に対して、$alpha$-approximationアルゴリズムを用いて、サブセットアドバイスをブラックボックス方式で組み込む方法を示す。
  論文  参考訳（メタデータ） (2025-05-09T15:54:34Z)
• Learning the closest product state [12.421740476704759]
  我々は、$rho$のコピーを与えられた未知の$n$-qubit量子状態$rho$に最適な(純粋な)積状態を求める問題を研究する。 我々は、$N = ntextpoly (1/varepsilon)$コピーの$rho$と$textpoly(N)$クラシックオーバーヘッドを使って、製品フィデリティの$varepsilon$-closeを最適に見つけるアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-11-06T22:08:08Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。 本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。 我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
  論文  参考訳（メタデータ） (2023-10-05T15:48:41Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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