Formalizations of theorems from papers submitted to ACM STOC 2027 (the 59th Annual ACM Symposium on Theory of Computing). Paper list: https://sigact-stoc.github.io/stoc2027/ . Missions here state a main result of a STOC 2027 paper in Lean 4 with Mathlib; each mission's title begins with the paper title.
Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with Θ(n) ancilla qubitsResearch Paper
Preparing the Gibbs stateρβ=e−βH/Tre−βH of a many-body Hamiltonian is a basic task of quantum simulation: it is the input to thermal expectation values, to quantum algorithms for optimization and sampling, and to studies of quantum phases at finite temperature. One family of algorithms mimics physical thermalization.…
Quasipolynomial Trace ReconstructionResearch Paper
A deletion channel with retention probabilityp takes a binary string x∈{0,1}n, keeps each bit independently with probability p, and outputs the kept bits in order; the output is a trace. The trace reconstruction problem asks how many independent traces are needed to recover an unknown x with probability at least 2/3. It is a basic question about…
Effective Horizons for Prophet Inequalities with Discounted I.I.D. RewardsResearch Paper
A prophet inequality compares a gambler, who sees rewards one at a time and must accept or reject each irrevocably, with a prophet who knows all rewards in advance. For n i.i.d. rewards, a threshold rule with per-stage acceptance probability about 1/n guarantees a fraction 1−1/e of the prophet's expected reward, and for independent non-identical rewards the…
Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal ApproximationResearch Paper
When every player of a game has regret o(T), the empirical distribution of play converges to the set of coarse correlated equilibria, at a rate governed by the largest average regret. This link is why the dependence of regret on the horizon T has been studied closely. Against an adversary the rate Tlogn cannot be improved, but a player in a game…
Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex CaseResearch Paper
Gradient descent (GD) with a predetermined stepsize scheduleH=(h1,…,hn)∈[0,∞)n runs xt=xt−1−ht∇F(xt−1) with stepsizes fixed before the optimization starts. It is the simplest first-order method, and the question of how fast it can be made to converge by choosing H well, without momentum, line search or adaptivity, has been…
Pareto-optimal Non-Clairvoyant Scheduling with PredictionsResearch Paper
Non-clairvoyant scheduling asks how to run n jobs on one machine, preemptively, so as to minimize the sum of their completion times, when the size of a job is learned only when it completes. If the sizes were known, running the jobs in increasing order of size (Shortest Processing Time first, Smith's rule) would be optimal. Without them, Round-Robin, which…
Matrix Lewis Weights: Solving Semidefinite Programs in Square Root Constraints IterationsResearch Paper
A semidefinite program with m variables and an n×n matrix constraint asks to minimize c⊤x subject to ∑i=1mxiAi−C⪰0. Interior point methods follow the central path of a self-concordant barrierf for the feasible region; the classical analysis of Nesterov and Nemirovskii (1994) takes O(Kνlog(1/ε)) iterations…
Minimum-Mean Testing under Metric Constraints:Shared Information, Certificates, and AdaptivityResearch Paper
Many verification tasks ask whether every one of k noisy quantities clears a threshold: a batch passes inspection only if every component meets its specification, and an update is deployed only if every task benefits. When the quantities are known to be related, one observation carries evidence about several possible failures at once. Chaomeng Chen and…
Interior Point Methods Solve Random LPs in polylog(n) iterationsResearch Paper
Interior point methods (IPMs) and the simplex method are the standard tools for solving linear programs in practice. Path-following IPMs carry a worst-case guarantee of O(nlog(1/ε)) iterations, proved in 1988–1989 (Renegar; Kojima–Mizuno–Yoshise; Monteiro–Adler) and never improved since. Production codes, however, solve programs with…
Exponential memory/query-complexity tradeoffs in high-accuracy feasibility problemsResearch Paper
Cutting-plane methods solve convex feasibility problems with an optimal number of separation-oracle queries, but they store a description of the current localization set, about d2log(1/ϵ) bits. Gradient-type methods need only O(dlog(1/ϵ)) bits but converge polynomially. Whether low memory forces a large query cost is a question about the…
Adaptive Variance Reduction across Smoothness and Noise ConditionsResearch Paper
Stochastic first-order methods for smooth nonconvex objectives are analysed under one of several oracle conditions, and the attainable rate depends on which one holds. With unbiased gradients of bounded variance, E∥∇f∥ can be driven to O(T−1/4) after T gradient queries (Ghadimi–Lan 2013). When the stochastic gradients are also smooth on…
Online Learning with Ordered Experts (via Two-point Feedback)Research Paper
Many online decisions choose a point on an ordered scale: a posted price, a threshold, an inventory level. When a class of experts recommends such points, the learner would like to compete with the best expert while paying for only a few loss evaluations per round. Zuo (Online Learning with Ordered Experts (via Two-point Feedback), STOC 2027 submission)…
A Matrix Lee-Sidford Barrier and Faster Semidefinite ProgrammingResearch Paper
A semidefinite program (SDP) optimizes a linear function over the intersection of the cone of positive semidefinite matrices with an affine subspace. SDPs model relaxations of combinatorial problems, control and sum-of-squares certificates, and their fastest general-purpose solvers are interior point methods, which follow a central path defined by a self-con…
Newton Steps are Faster for Linear Complementarity ProblemsResearch Paper
The linear complementarity problem (LCP) asks, for a matrix M∈Rn×n and a vector q∈Rn, for vectors x,s with Mx+q=s, x⊤s=0 and x,s≥0. It contains the optimality conditions of linear and convex quadratic programs, and discounted stochastic games, mean-payoff and parity games reduce to it. For general M the problem is…
Auction-Based Algorithms for Weighted Matroid Intersection with Near-Linear Query ComplexityResearch Paper
Matroid intersection asks for a largest (or heaviest) set that is independent in two matroids at once. It contains bipartite matching, arborescences, rainbow spanning trees and many scheduling and assignment problems as special cases, and it is one of the few problems where combinatorial optimization has an exact polynomial-time theory beyond network flows…
Near-Optimal Regret in U-Calibration for Every Proper LossResearch Paper
In prediction as a service, a forecaster publishes probability forecasts over K outcomes that many downstream decision makers use, each with its own loss. U-calibration (Kleinberg et al., COLT 2023) asks for a single forecasting algorithm whose regret is small for every proper loss at the same time, so that the forecasts are trustworthy for all of these…
Scheduling Jobs to Maximize Minimum Fractional CompletionResearch Paper
Most scheduling objectives value a job only once it is finished. In an overloaded system that view is too coarse: when there is not enough processing time to finish everything, a scheduler can still make useful partial progress on many jobs. Max-min fractional scheduling asks for the schedule that maximizes the smallest fraction of work completed on any…
Optimal Marginal Convergence for Transvection-Walk-Based Trapdoored Matrices over Large FieldsResearch Paper
A trapdoored matrix is a matrix that is computationally indistinguishable from a uniformly random one, yet admits fast matrix–vector multiplication given a secret key. The notion was formalized by Braverman and Newman and by Vaikuntanathan and Zamir in 2026, and it already underlies protocols for private inference, delegated linear algebra and private…
Omniprediction for All Mixable Proper Losses and BeyondResearch Paper
A forecaster that outputs probabilities is usually trained against one loss function, yet its forecasts are often consumed by several downstream decision makers, each with its own loss, some of them unknown at training time. Omniprediction, introduced in the batch setting by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389) and in the online…
Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform ConvexityResearch Paper
Uniform convexity of degree q strengthens strong convexity by a curvature term qσ∥y−x∥q; it appears in high-order optimization and in machine learning. Methods with access to derivatives up to order p are compared on functions whose pth derivative is Hölder continuous with exponent ν and parameter H. The optimal number of oracle calls…
Tilted Convexity and an Exact Offline–Online SeparationResearch Paper
Convexity of a function f has three standard first-order descriptions: the support inequalityf(y)−f(x)≥⟨y−x,v⟩ for subgradients v, monotonicity of the subdifferential, and the increase of secant slopes along lines. Many losses in learning and optimization are not convex but keep a quantitative fraction of these properties, and online…
Near-Optimal K-Regret for Online Learning in Uninformed Markov GamesResearch Paper
A learner repeatedly plays an episodic two-player Markov game against an opponent it cannot see. It observes its own actions, its losses and the states, but not the opponent's actions, its policy or even its action set. This uninformed setting models online decision making against other agents whose behaviour is hidden, for example a market participant…
Sharp Bounds for Truthful-in-Expectation SchedulingResearch Paper
In scheduling on unrelated machines, each of m indivisible jobs takes a possibly different processing time on each of n machines, and the goal is to minimize the makespan, the largest machine load. When the processing times are known, Lenstra, Shmoys and Tardos give a polynomial-time 2-approximation. Nisan and Ronen (NR01) introduced the strategic version:…
Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the O(N) ModelResearch Paper
Glauber dynamics is the standard Markov chain for sampling from a spin system: pick a uniformly random site, forget its spin, and resample it from the conditional law given all other spins. Its spectral gap controls mixing and the variance of Monte Carlo estimates. A family of local-to-global results bounds this global gap by quantities computed on two-site…
Optimal Auctions for Anchored Bidders under a Rational Revenue GuaranteeResearch Paper
Auctions are increasingly run on behalf of users by automated agents. Some of these agents behave like textbook rational bidders and play a Bayes–Nash equilibrium; others are anchored: they submit their user's value as the bid, whatever the mechanism. A seller facing both populations wants a mechanism that earns as much as possible from anchored bidders…