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.
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…
Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion ProblemsResearch Paper
Convex-concave min-max problems, monotone variational inequalities and nonexpansive fixed-point problems can all be written as monotone inclusions: find a zero of the sum of two monotone operators. A natural accuracy measure for such problems is the tangent residual, the distance from the origin to the set of operator values at a point; it reduces to the…
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…
An Ω(N) Lower Bound for Path Following Interior Point Methods on Single-Source Shortest PathsResearch Paper
Path following interior point methods (IPMs) are the fastest known way to solve general linear programs in theory, and a core component of practical solvers. For a linear program with N inequality constraints, the classical analysis (Renegar 1988) reduces the duality gap by a constant factor every O(N) iterations. Practical solvers need far fewer…
Online Load Balancing under Symmetric NormsResearch Paper
In online load balancing, jobs arrive one at a time and each must be placed on one of M machines, irrevocably, before the next job is seen. The cost is a function of the final vector of machine loads. The classical objective is the makespan, the largest load; Graham's 1966 list-scheduling rule is (2−1/M)-competitive for it on identical machines (Graham 1966)…
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤21+\epsResearch Paper
The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: n Ising spins interacting through a symmetric Gaussian matrix. Sampling from its Gibbs measure is a standard average-case test problem for Markov chain Monte Carlo, because the interactions are dense, of both signs, and random. The natural chain is Glauber dynamics: pick a site uniformly…
Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier RankResearch Paper
A convex body is usually available only through an oracle. In the membership oracle model, an algorithm may ask whether a point lies in a body K⊆Rn, given radii with B2(0,r)⊆K⊆B2(0,R), and it must return a nearly optimal point for a linear objective. Classically this costs a polynomial number of membership queries, and…
Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness ThresholdResearch Paper
The ferromagnetic Ising model is a basic model of magnetism, and sampling its Gibbs law gives access to magnetization, spin correlations and other observables. Polynomial-time sampling has been known since Jerrum and Sinclair and Randall and Wilson, so the remaining question is how small the exponent can be. On a graph of maximum degree Δ the parameter …
Local-to-Global Theorems Based on Cones with Applications to Graph ColoringResearch Paper
A proper list coloring of a graph assigns to every vertex a color from its own list so that adjacent vertices get different colors. Sampling a uniformly random proper coloring is a benchmark problem for Markov chain Monte Carlo, for approximate counting, and for the statistical physics of the antiferromagnetic Potts model. The standard sampler is the Glauber…