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.
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…
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick modelResearch Paper
The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: n binary spins coupled pairwise by independent Gaussian interactions of both signs (SK75). Its equilibrium theory (replica symmetry breaking, the Parisi formula, the cavity method and the Thouless–Anderson–Palmer (TAP) equations) is a central part of the probability of disordered systems (T…
Improved Integrality Gap for Multicommodity Flow on TreesResearch Paper
Unit-demand multicommodity flow on trees is a basic routing problem in approximation algorithms. A tree network has integer edge capacities, and each request asks to route one unit between two vertices along the unique tree path joining them. The goal is to accept a maximum-weight set of requests without exceeding any capacity. The problem is NP-hard and…
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual SettingsResearch Paper
Minimizing a convex function from first-order information is the basic model of large-scale optimization: an algorithm queries points xt and receives the value f(xt) and a subgradient gt. Its oracle complexity is the error it can guarantee after T queries, uniformly over a class of functions. When the feasible set is the unit ball of a norm ∥⋅∥p an…
Decoupling Corruption and Horizon in Robust Contextual PricingResearch Paper
In dynamic pricing a seller repeatedly posts a price to an arriving buyer and learns only whether the buyer bought. In the contextual version, each buyer comes with an observable feature vector, and the buyer's valuation is a fixed but unknown linear function of it. The seller must learn that linear function from yes/no answers while losing as little…
Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared RandomnessResearch Paper
Consider m devices sharing K wireless channels. In each time slot every device transmits on one channel, two devices on the same channel both fail, channel qualities change arbitrarily, and a device learns only what it transmitted itself. A device that transmitted nothing cannot tell a bad channel from a collision. This is the multiplayer bandit problem…
Autonomous Quantum Memories from Classical Stochastic ProcessesResearch Paper
A quantum memory stores a qubit for a long time under noise. Passive or autonomous memories do this without measurements and classical feedback: the protection is built into the physical dynamics, typically a Lindblad master equation combining a stabilizer Hamiltonian, local dissipative corrections and noise. The best-known example is the four-dimensional…
Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature ReuseResearch Paper
Quasi-Newton methods build a curvature model from gradients alone and use it to take steps that are longer than those of a first-order method. Their classical theory is local. A line of work by Jiang, Jin and Mokhtari embedded quasi-Newton models in the hybrid proximal extragradient (HPE) framework of Monteiro and Svaiter and obtained global, non-asymptotic…
Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope SchedulingResearch Paper
Many computing and production systems share resources among jobs whose sizes are unknown when they arrive: a cluster splits processors among tasks, a network splits link capacity among flows, a factory splits machines among orders. A scheduler that never learns a job's size until the job finishes is called nonclairvoyant. On a single machine the right…
Concentration Inequalities for Branching Random Walks with Applications to Phase Transitions in CSPsResearch Paper
Many random processes in the analysis of algorithms and random structures are sums Sn=X1+⋯+Xn whose increments are neither independent, nor martingale differences, nor bounded. The sequential generation of random K-SAT and q-colouring instances is the example that drives Liu and Zhang: each step applies random clauses to the current formula, and…
Sampling from the Sherrington–Kirkpatrick Model up to CriticalityResearch Paper
The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: an Ising model on N spins in which every pair interacts through an independent Gaussian coupling. It is a standard testbed in statistical physics, probability and the analysis of algorithms, and sampling from its Gibbs measure in the high-temperature regime 0≤β<1 has been a central…
Signal-Routed Two-Arm Verification: Statistical Soundness and Threshold AggregationResearch Paper
A verifier of an interactive proof or succinct argument ends with one bit, but its view carries graded evidence: how many local consistency tests passed, whether the messages were well formed. A verifier that processes many statements under a budget would like to spend little effort on rounds that look clean and more on rounds that look suspicious. Any such…
Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman DecisionsResearch Paper
A Bellman decision compares the scores of a few actions, each built from maxima of a shared critic: ta(Q)=ra+γ∑iwaimaxh≤KiQi(h) with 0<γ<1. In approximate dynamic programming and value-based reinforcement learning the critic is learned from costly scalar values, so a basic question is how much information about the critic a…
Optimal Subcubic Byzantine Agreement with Plain PKIResearch Paper
Byzantine agreement (BA) asks n parties, up to t of which are malicious (byzantine), to agree on a common bit. It is the basic primitive behind replicated state machines and blockchains. In the synchronous model without any setup it is solvable only for t<n/3 (Pease–Shostak–Lamport 1980). With a public-key infrastructure (PKI), where every party can sign…
Sketching Language Models for Context AttributionResearch Paper
Context attribution asks how parts of a prompt affect a chosen measurement of a language model's output. For a prompt with n tokens, leave-one-out attribution records the measurement after deleting each token individually. Direct evaluation takes n model calls. Liaw, Mehta, Velegkas and Zhou study when all these values can be estimated with fewer calls,…
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular OrienteeringResearch Paper
A Markov decision process (MDP) is the standard model of sequential decision making under uncertainty in operations research and reinforcement learning (Puterman 1990). In the classical model the agent collects an additive reward over a finite horizon H, and an optimal policy that depends only on the current state and time is found by dynamic programming.
Fast Quantum Byzantine Agreement with Nearly Linear Quantum CommunicationResearch Paper
In Byzantine agreement, n processes with input bits must decide a common bit although up to t of them behave arbitrarily [PSL80]. Randomized protocols reach agreement quickly when enough common coins are available: random bits that all honest processes obtain identically and that the adversary cannot predict before they are used [BO83, Rab83]. Against a full…
Failure of Symmetry of Information for Quantum ComputationsResearch Paper
Symmetry of information is the identity K(x,y)=K(x)+K(y∣x)±O(log(∣x∣+∣y∣+2)) for plain Kolmogorov complexity (Zvonkin–Levin 1970). It says that the information in a pair splits additively into the information in the first string and the information in the second given the first. Whether this survives time bounds is a long-standing question of…
Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp GeometriesResearch Paper
Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2: the feasible region is an ℓp ball and the Lipschitz…
A Witnessing Duality for ReLU Network DepthResearch Paper
How many hidden layers a ReLU network needs to compute max(x1,…,xn) exactly is a basic question about the expressiveness of depth. Exact representation questions of this kind are studied for real, rational and integer weights. For integer weights, Haase, Hertrich and Loho (arXiv:2302.12553) proved a logarithmic depth lower bound by a modular argument…