In a linear reconstruction game, an unknown point x* ∈ ℝᵈ is estimated from noisy linear queries. In each round, we choose a direction v and receive an answer within δ of the inner product ⟨v,x*⟩. The goal is to understand the best worst-case error achievable after T queries.
I will explain how this interaction is connected to the geometry of ℝᵈ. After T queries, the possible locations of x* consistent with the answers form a feasible region, and the optimal worst-case error is governed by the radius of its minimum enclosing ball. This brings in a classical relation between diameter and minimum-enclosing-ball radius, given by Jung’s theorem (1901).
Building on this viewpoint, I will present our main results. In the limit of infinitely many queries, the optimal error is exactly √(2d/(d+1))δ. In fixed dimension, the excess error above this limiting value decays doubly exponentially fast in the number of queries. When the dimension grows, there is an exponential query threshold: exponentially many queries are necessary and sufficient to make the excess error vanish.
The main technical ingredient is a robust version of Jung’s theorem, showing that near-extremal feasible regions have their extremal parts clustered near a regular simplex. I will discuss how this structure leads to the doubly exponential rate, and, time permitting, sketch the proof of the robust Jung theorem.
The talk is based on joint work with Yuval Filmus and Shay Moran, accepted to COLT 2026.