Learning discrete distributions from batched user data under person-level privacy is a fundamental problem in federated analytics. This paper develops the first polynomial-time pure-DP algorithm that matches the information-theoretic sample complexity up to logarithmic factors, via a new degree-6 sum-of-squares certificate based on a trace-bounded diagonal majorizer for multinomial covariance. It also proves a statistical-query lower bound suggesting the gap between efficient and optimal robust rates may be inherent.

LLM-native advertising introduces new auction-design challenges because an ad’s click-through rate depends on its context passage and earlier ads steal clicks from later ones under a first-click cascade. This paper studies truthful mechanism design when the LLM answer and its passage order are fixed before bidding, showing that a constant-factor welfare approximation is compatible with truthfulness even under this editorial-order restriction. The authors propose click thinning—randomly omitting earlier ads to equalize click services across positions—which turns welfare maximization into a tractable linear-fractional matching problem and yields an elegant optimal tradeoff between approximation, truthfulness, and computational efficiency.

The paper studies proper hypothesis selection: given $n$ candidate distributions and sample access to an unknown target $P$, the goal is to return one candidate with total variation distance at most $3\min_i d_{TV}(P,H_i)+\varepsilon$. The core idea is to maintain weights over the candidates, define a weighted median of their densities as an unnormalized intermediate measure, and perform multiplicative weight updates using balanced tests derived from this median. The result achieves the optimal factor-3 approximation and sample complexity $O(\varepsilon^{-2}\log(n/\delta))$ while improving the running time to $O(n\varepsilon^{-2}\log(n/\delta))$, answering an open question of Aamand et al. (COLT 2026) by reducing the failure-probability dependence from $1/\delta$ to $\log(1/\delta)$.

Robust Markov decision processes with polyhedral uncertainty lack exact convex representations because the natural robust Bellman inequalities become bilinear or union-of-polyhedra constraints. This paper shows how to encode a finite sequence of robust policy-iteration steps into a single exact LP whose optimal face recovers the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length, and the authors use this representation together with a unified complexity analysis to prove strongly polynomial bounds for several standard uncertainty sets—including $\ell_1$, weighted $\ell_1$, interval, and Wasserstein—that previously lacked such guarantees.

We study non-clairvoyant single-machine scheduling to minimize the sum of completion times, a problem for which no constant-competitive algorithm is possible in the pure setting. The authors introduce a robustness framework that leverages a classifier's confusion matrix to partition jobs into predicted classes, characterizing uncertainty as internal permutations rather than numerical scenarios. This structural information yields an oblivious non-adaptive Min-Cost algorithm that is simultaneously optimal for multiple criteria, alongside new adaptive and randomized extensions.

This paper formalizes the transformer context window as an I/O page and proves that tool-augmented agents with indexed external memory achieve exponential retrieval cost savings over sequential scanning: $\mathcal{O}(\log_b N)$ versus $\Omega(N)$ page reads. The authors validate these predictions experimentally across three content types and identify "parametric memory competition" as a failure mode where models bypass retrieval protocols for familiar content.