$k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture

• URL: http://arxiv.org/abs/2604.07240v1
• Date: Wed, 08 Apr 2026 16:06:43 GMT
• Title: $k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture
• Abstract summary: We introduce a code-based challenge for automated, open-ended mathematical discovery based on the $k$-server conjecture.<n>The task is to discover a potential function satisfying a large graph-structured system of simple linear inequalities.<n>Our results suggest that the task is challenging but plausibly within reach of current methods.
• Score: 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.

Related papers

• The Time-Space Complexity of Checking Multiple Assertions in Quantum Programs [0.5524804393257919]
  checking a quantum program that contains multiple assertions often requires using additional space or running the program additional times.<n>For a program with $n$ assertions, a naive strategy uses $n$ ancillas to learn all $n$ outcomes.<n>An alternative uses one ancilla but repeats program execution over $n$ rounds, checking one assertion per round.
  arXiv  Detail & Related papers  (2026-07-13T15:09:04Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
  We study mean estimation of a random vector $X$ in a distributed parameter-server-worker setup.<n>Key challenges are adversarial measurements and asynchrony.<n>Results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers.
  arXiv  Detail & Related papers  (2026-04-07T11:45:55Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  We present a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets.<n>With negligible computational overhead, $textttPT-LiRPA$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output.
  arXiv  Detail & Related papers  (2025-07-07T18:45:53Z)
• Solving Inequality Proofs with Large Language Models [42.667163027148916]
  Inequality proving is crucial across diverse scientific and mathematical fields.<n>This makes it a demanding frontier for large language models (LLMs)<n>We release IneqMath, an expert-curated dataset of Olympiad-level inequalities.
  arXiv  Detail & Related papers  (2025-06-09T16:43:38Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• A De-singularity Subgradient Approach for the Extended Weber Location Problem [12.263117303066831]
  We establish a de-singularity subgradient approach for the extended Weber location problem. We show that the proposed approach solves the problem, produces the same results as in the non-singularity cases, and shows a reasonable rate of linear convergence.
  arXiv  Detail & Related papers  (2024-05-11T09:22:44Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• High-Dimensional Experimental Design and Kernel Bandits [9.401375475860561]
  Methods from optimal linear experimental design have been leveraged to obtain state of the art results for linear bandits. A design returned from an objective such as $G$-optimal design is actually a probability distribution over a pool of potential measurement vectors. We propose a rounding procedure that frees $N$ of any dependence on the dimension $d$.
  arXiv  Detail & Related papers  (2021-05-12T17:10:56Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  We introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, approximate degreelemma, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore.
  arXiv  Detail & Related papers  (2020-02-25T11:46:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.