論文の概要: $k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture

• arxiv url: http://arxiv.org/abs/2604.07240v1
• Date: Wed, 08 Apr 2026 16:06:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.624758
• Title: $k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture
• Title（参考訳）: $k$-server-bench:$k$-Server Conjectureの潜在的な発見を自動化する
• Authors: Kirill Brilliantov, Etienne Bamas, Emmanuel Abbé,
• Abstract要約: 我々は、$k$-server予想に基づいて、自動でオープンな数学的発見のためのコードベースの挑戦を紹介する。 この課題は、単純な線形不等式からなる大きなグラフ構造系を満たすポテンシャル関数を発見することである。 以上の結果から,現在の手法の範囲内において,課題は困難である可能性が示唆された。
• 参考スコア（独自算出の注目度）: 4.29490433621832
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a code-based challenge for automated, open-ended mathematical discovery based on the $k$-server conjecture, a central open problem in competitive analysis. The task is to discover a potential function satisfying a large graph-structured system of simple linear inequalities. The resulting evaluation procedure is sound but incomplete: any violated inequality definitively refutes a candidate, whereas satisfying all inequalities does not by itself constitute a proof of the corresponding conjecture's special case. Nevertheless, a candidate that passes all constraints would be strong evidence toward a valid proof and, to the best of our knowledge, no currently known potential achieves this under our formulation in the open $k=4$ circle case. As such, a successful candidate would already be an interesting contribution to the $k$-server conjecture, and could become a substantial theoretical result when paired with a full proof. Experiments on the resolved $k=3$ regime show that current agentic methods can solve nontrivial instances, and in the open $k=4$ regime they reduce the number of violations relative to existing potentials without fully resolving the task. Taken together, these results suggest that the task is challenging but plausibly within reach of current methods. Beyond its relevance to the $k$-server community, where the developed tooling enables researchers to test new hypotheses and potentially improve on the current record, the task also serves as a useful \emph{benchmark} for developing code-based discovery agents. In particular, our $k=3$ results show that it mitigates important limitations of existing open-ended code-based benchmarks, including early saturation and the weak separation between naive random baselines and more sophisticated methods.
• Abstract（参考訳）: 我々は、競合分析における中心的なオープン問題である$k$-server予想に基づいて、自動的かつオープンな数学的発見のためのコードベースの挑戦を紹介する。 この課題は、単純な線形不等式からなる大きなグラフ構造系を満たすポテンシャル関数を発見することである。 しかし、すべての不等式を満たすことは、それ自体が対応する予想の特別な場合の証明を構成するわけではない。 それでも、全ての制約を通した候補は、有効な証明に対する強い証拠であり、我々の知識の限りでは、現在知られているポテンシャルは、オープンな$k=4$円の場合において、私たちの定式化の下では達成できない。 したがって、成功した候補は、既に$k$-server予想への興味深い貢献であり、完全な証明と組み合わせれば、かなりの理論的結果になる可能性がある。 解決された$k=3$レジームの実験は、現在のエージェントメソッドが非自明なインスタンスを解決できることを示し、オープンな$k=4$レジームでは、タスクを完全に解決することなく既存のポテンシャルに対する違反の数を減らす。 これらの結果から,課題は挑戦的ではあるが,現在の手法の範囲内にあることが示唆された。 開発ツールによって、研究者が新しい仮説をテストし、現在の記録を改善できるだけでなく、コードベースの発見エージェントを開発する上で有用なemph{benchmark}としても機能する。 特に、$k=3$の結果は、初期飽和や単純なランダムなベースラインとより洗練されたメソッドの弱い分離を含む、既存のオープンエンドのコードベースのベンチマークの重要な制限を緩和していることを示している。

関連論文リスト

• Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
  分散パラメータ-サーバ-ワーカー設定における乱数ベクトル$X$の推定について検討する。 主な課題は、敵の計測と非同期である。 その結果, 分散線形推定におけるロバスト性, 識別性, 統計的効率の統一的有限時間評価が得られた。
  論文  参考訳（メタデータ） (2026-04-07T11:45:55Z)
• Solving Inequality Proofs with Large Language Models [42.667163027148916]
  不等式証明は様々な科学・数学分野において不可欠である。 これにより、大きな言語モデル(LLM)の需要が高まるフロンティアとなる。 我々は、Olympiadレベルの不平等を専門家が計算したデータセットであるIneqMathをリリースした。
  論文  参考訳（メタデータ） (2025-06-09T16:43:38Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• A De-singularity Subgradient Approach for the Extended Weber Location Problem [12.263117303066831]
  拡張Weber ロケーション問題に対する非特異な下位段階のアプローチを確立する。 提案手法はこの問題を解き、非特異性の場合と同じ結果を示し、線形収束の合理的な速度を示す。
  論文  参考訳（メタデータ） (2024-05-11T09:22:44Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• High-Dimensional Experimental Design and Kernel Bandits [9.401375475860561]
  最適な線形実験設計の手法を利用して、線形バンディットの最先端の結果を得ています。 G$-optimal designのような目的から返される設計は、実際に潜在的な測定ベクトルのプール上の確率分布である。 我々は、次元 $d$ に対する任意の依存から$n$ を解放する丸め手順を提案する。
  論文  参考訳（メタデータ） (2021-05-12T17:10:56Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。 ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。 また、Impagliazzoのハードコアの改良版も証明した。
  論文  参考訳（メタデータ） (2020-02-25T11:46:08Z)

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

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