Ernest van Wijland
PhD student at IRIF, Université Paris-Cité. I am fortunate to have Claire Mathieu (CNRS) and Vincent Cohen-Addad (Google Research) as my advisors.
My research interests include Optimization, Algorithms, and AI. I am currently working on AI's reasoning abilities, and on approximation algorithms for clustering and network design.
| Email: | ernest(dot)vanwijland(at)irif(dot)fr |
Publications (Google Scholar)
-
Efficient Prover–Estimator Debate via Signed Level-Set Optimization
In SubmissionRecursive debate makes complex claims verifiable by reducing them to subclaims that a human can eventually judge. Its weakness is obfuscation: a dishonest prover can hide an error among subclaims that an honest opponent cannot efficiently identify. Brown-Cohen et al. (2026) introduced prover-estimator debate, replacing the search for a false subclaim with probabilistic predictions over all submitted subclaims. Their work showed that suitable probability estimators exist, but their argument uses reference answers unavailable to the estimator, which they note makes it non-executable, and provides a circuit-size upper bound exponential in the branching width. We here explore the conditions under which estimators can instead be constructed efficiently. When decompositions cannot profitably change the meaning of a claim, estimator construction reduces to local optimization guided by whether the prover alleges that the current estimate is too high or too low. Assuming efficient signed level-set optimization, our algorithm uses resettable access to a fixed prover and simulated debate scores, never hidden reference answers, and outputs an estimator satisfying a soundness bound against that prover, with construction and evaluation costs polynomial in the mechanism's parameters. Conversely, without this semantic restriction, a uniform compiler for a promised class of instances would yield randomized polynomial-time algorithms for every polynomial-time verifiable total search relation, even when the local gates are projections or constants. Thus, efficient local optimization alone is insufficient in the worst case.
-
TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability
In SubmissionWe introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem-proving tasks from papers published at top theoretical computer science venues (STOC, FOCS, and SODA). Each task provides the necessary context to derive a self-contained proof for a target result. We evaluate state-of-the-art models on this benchmark. We verify the correctness of generated proofs via a verification agent, and further benchmark the verifier against human-expert proof judgements on a set of target statements and generated proofs pairs. Our reference verifier achieves over 90% accuracy on the expert labeled set. The tasks are publicly available here.
-
Spectral Dual Fitting for \(k\)-Means
SODA 2027We give a new dual fitting algorithm which gives improved approximation ratios of \(3+\ln 2 + \varepsilon\ (\approx 3.694)\) and \(4.9+\varepsilon\) for \(k\)-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of \(4+\varepsilon\) [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and \(5+\varepsilon\) [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean \(k\)-Means breaks the hardness barrier of \(1+8/e\approx 3.94\) for Metric \(k\)-Means. Prior to our work, no such separation between general and Euclidean metrics was known for \(k\)-Median, \(k\)-Means, or Facility Location in terms of their approximability.
Unlike prior dual fitting approaches for \(k\)-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm. -
Learning Augmented Online Multi-Level AggregationIn SubmissionAggregation is a classic problem in network design. Here, we study one of its most famous variants, the online Multi-Level Aggregation problem with Deadlines (MLAP-D). Given a rooted tree with node costs, requests arrive over time at the tree nodes, each request must be served by its deadline, and requests that are pending at a common time can be aggregated and served together. The cost of serving a set of requests together is the total cost of the minimal subtree spanning all nodes containing those requests (and the root), and the objective is to minimize the sum of the costs of the nodes in the subtrees used to serve all requests.
The best known online algorithms are \(O(\hbox{depth})\)-competitive, whereas the strongest known online lower bound is \(4\)-competitiveness. In this paper, we initiate the theoretical study of learning augmented MLAP-D. Leveraging the existence and structure of a constant approximation algorithm in the offline setting, we consider a simple online algorithm, \(SampleAndAugment\), and prove that for three natural stochastic models, it is \(4\)-competitive in expectation. This matches the adversarial setting lower bound. We complement these results with reductions demonstrating that our stochastic assumptions are necessary; if they are relaxed, the problem remains as difficult as the general worst-case adversarial setting. -
A \((4+\varepsilon)\)-Approximation for Euclidean \(k\)-Means via Non-Monotone Dual Fitting
STOC 2026We present a polynomial-time \( (4+\varepsilon) \)-approximation algorithm for (high-dimensional) Euclidean \( k \)-Means. This substantially improves on the current-best 5.83-approximation in [Charikar, Cohen-Addad, Gao, Grandoni, Lee, Van Wijland - FOCS'25] (that also works for the metric case).
The mentioned algorithm by Charikar et al. critically exploits a greedy Lagrangian Multiplier Preserving (LMP) approximation for Facility Location with squared metric distances, that adapts the classical greedy algorithm with dual-fitting analysis for Metric Facility Location in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM'03]. The authors then turn it into an approximation algorithm for (Metric) \( k \)-Means, at the cost on an extra factor \( 1+\varepsilon \), by exploiting the framework introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC'25] for \( k \)-Median.
Our main contribution is a greedy LMP 4-approximation for Facility Location with squared Euclidean distances. Differently from Charikar et al., our algorithm sometimes decreases the dual variables, a quite uncommon feature for dual-based algorithms. This is critical in our dual-fitting analysis in order to exploit the specific properties of Euclidean metrics. For the \( (4+\varepsilon) \)-approximation for \( k \)-Means, we extend the framework by Cohen-Addad et al. by overcoming substantial technical challenges posed by decreased dual values. -
An Improved Greedy Approximation for (Metric) \(k\)-Means
FOCS 2025Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the \( k \)-Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into \( k \) clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers.
In this paper, we present a polynomial-time \( 3+2\sqrt{2}+\varepsilon<5.83 \)-approximation algorithm for \( k \)-Means in general metrics. This substantially improves on the current-best \( (9+\varepsilon) \)-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS'17, SICOMP'20], and even slightly improves on the \(5.92\)-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC'22] for the Euclidean special case.
A natural approach for \( k \)-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for \( k \)-Means build upon an adaptation of an LMP \(3\)-approximation for facility location with metric connection costs in [Jain, Vazirani - J.ACM'01] based on a primal-dual method, rather than on the improved LMP greedy \(2\)-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM'03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC'25] for the related (metric) \( k \)-Median problem. -
Faster Approximation Scheme for Euclidean \(k\)-TSP
SOCG 2024In the Euclidean \( k \)-traveling salesman problem (\( k \)-TSP), we are given \( n \) points in the \( d \)-dimensional Euclidean space, for some fixed constant \( d \geq 2 \), and a positive integer \( k \). The goal is to find a shortest tour visiting at least \( k \) points. We give an approximation scheme for the Euclidean \( k \)-TSP in time \( n \cdot 2^{O(1/\varepsilon^{d-1})} \cdot (\log n)^{2d^2 \cdot 2^d} \). This improves Arora's approximation scheme of running time \( n \cdot k \cdot (\log n)^{\left(O\left(\sqrt{d}/\varepsilon\right)\right)^{d-1}} \) [J. ACM 1998]. Our algorithm is Gap-ETH tight and can be derandomized by increasing the running time by a factor \( O(n^d) \).
-
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
MOOR 2023We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either \(1\) or \( p/q \) for some fixed coprime numbers \( p, q \in \mathbb{N} \) such that \( 1 \leq q < p \). Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the value of \( q \). We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, \( q = 1 \). We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, \( q = 2 \). Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever \( q \geq 3 \).
-
Maximizing Nash Social Welfare in 2-Value Instances
AAAI 2022We consider the problem of maximizing the Nash social welfare when allocating a set \( G \) of indivisible goods to a set \( N \) of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either \( p \) or \( q \), where \( p \) and \( q \) are integers and \( p \ge 2 \). In terms of approximation, we present positive and negative results for general \( p \) and \( q \). We show that our algorithm obtains an approximation ratio of at most \(1.0345\). Moreover, we prove that the problem is APX-hard, with a lower bound of \(1.000015\) achieved at \( p/q = 4/5 \).
Teaching
- Currently teaching assistant for the second year of Bachelor course "Programming Project" at Université Paris-Cité.
- Previously teaching assistant for the "Introduction to Python", "Algorithmics Concepts", and "Programming Project" courses.