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.
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…
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…
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…
Tight bounds for fractional and randomized truthful schedulingResearch Paper
In scheduling on unrelated machines, m tasks are assigned to n machines, machine i needs time tij for task j, and the goal is to minimize the makespan, the largest total processing time of a machine. Nisan and Ronen proposed this as the canonical problem of algorithmic mechanism design (NR01): each machine privately knows its row ti and is paid by the…
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 …