論文の概要: Reinforced Generation of Combinatorial Structures: Ramsey Numbers
- arxiv url: http://arxiv.org/abs/2603.09172v2
- Date: Wed, 11 Mar 2026 17:30:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-12 14:12:44.263342
- Title: Reinforced Generation of Combinatorial Structures: Ramsey Numbers
- Title（参考訳）: 組合せ構造の強化生成:Ramsey数
- Authors: Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta,
- Abstract要約: 5つの古典ラムゼー数に対する下界の改善を示す。
AlphaEvolveは1つのメタアルゴリズムで、検索結果の検索アルゴリズムを出力します。
- 参考スコア（独自算出の注目度）: 3.359365297148466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present improved lower bounds for five classical Ramsey numbers: $\mathbf{R}(3, 13)$ is increased from $60$ to $61$, $\mathbf{R}(3, 18)$ from $99$ to $100$, $\mathbf{R}(4, 13)$ from $138$ to $139$, $\mathbf{R}(4, 14)$ from $147$ to $148$, and $\mathbf{R}(4, 15)$ from $158$ to $159$. These results were achieved using AlphaEvolve, an LLM-based code mutation agent. Beyond these new results, we successfully recovered lower bounds for all Ramsey numbers known to be exact, and matched the best known lower bounds across many other cases. These include bounds for which previous work does not detail the algorithms used. Virtually all known Ramsey lower bounds are derived computationally, with bespoke search algorithms each delivering a handful of results. AlphaEvolve is a single meta-algorithm yielding search algorithms for all of our results.
- Abstract（参考訳）: 5つの古典ラムゼー数に対して改善された下界を示す:$\mathbf{R}(3, 13)$は$60$から$1$、$\mathbf{R}(3, 18)$は$99$から$100$、$\mathbf{R}(4, 13)$は$38$から$39$、$\mathbf{R}(4, 14)$は$47$から$48$、$\mathbf{R}(4, 15)$は$58$から$59$になる。
これらの結果は、LSMベースのコード突然変異剤であるAlphaEvolveを用いて達成された。
これらの新たな結果の他に、すべてのラムゼー数に対する下界は正確であることが知られ、他の多くのケースにおいて最もよく知られた下界と一致した。
これには、前回の作業が使用するアルゴリズムの詳細を記述していない境界が含まれている。
事実上すべての既知のラムゼーの下界は計算的に導出され、それぞれに少数の結果が与えられる。
AlphaEvolveは1つのメタアルゴリズムで、検索結果の検索アルゴリズムを出力します。
関連論文リスト
- The Complexity of Finding Local Optima in Contrastive Learning [18.910128965812124]
個別設定で$mathsfPLS$-hardness、連続設定で$mathsfPLS$-hardnessを証明します。
この結果から,アルゴリズムが様々なコントラスト学習問題の局所的最適解を見つけることは不可能であることが示唆された。
論文 参考訳（メタデータ） (2025-09-21T03:21:04Z) - Synthesis of Single Qutrit Circuits from Clifford+R [0.0]
2つの決定論的アルゴリズムが近似単一量子ゲートに提示される。
最初のアルゴリズムはクリフォード+$mathbfR$群を徹底的に探索する。
第2のアルゴリズムは、家庭用リフレクションを探索する。
論文 参考訳（メタデータ） (2025-03-26T03:55:43Z) - RamseyRL: A Framework for Intelligent Ramsey Number Counterexample
Searching [0.0]
ラムゼー数はノードの最小数、$n = R(s, t)$ であり、位数 $n$ のすべての無向単純グラフは位数 $s$ あるいは位数 $t$ の独立集合を含む。
本稿では,Ramsey数値に対する反例を見つけるために,最良1次探索アルゴリズムと強化学習(RL)手法の適用について検討する。
論文 参考訳（メタデータ） (2023-08-23T06:32:14Z) - 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) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions
and Approximations [6.2140753425381785]
我々は、$tildeOleft(C+d2K/Delta_minright)$の後悔を達成できる単純なアルゴリズムを提供する。
我々のアルゴリズムは非常に単純で、$sqrtd$で縛られた最もよく知られた後悔よりも悪いだけであり、以前の研究よりもはるかに低いオラクルの複雑さを持つ。
論文 参考訳（メタデータ） (2021-06-12T08:14:53Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。
また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T14:19:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。