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.
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…
Optimal Alternating Regret for Online Learning and GamesResearch Paper
In a repeated two-player game, the players can update simultaneously (both see only the past) or alternately (the second player sees the first player's current move before choosing). Alternating updates are known to speed up learning dynamics in zero-sum games (Wibisono, Tao, Piliouras, NeurIPS 2022; Cevher et al., NeurIPS 2023; Katona, Wang, Wibisono, JMLR…
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…
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…
The Optimal Sample Complexity of Multiclass and List LearningResearch Paper
In multiclass classification, a prediction rule assigns one label to each data point, and the set of possible labels may be infinite. Learning theory asks how much labeled data suffices to predict accurately on new points. The number of labels alone does not describe the difficulty of a hypothesis class. A useful complexity parameter must also distinguish…
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…
Monotone circuit lower bounds were first proved by Razborov's approximation method (Razborov 1985): every gate of a small circuit is replaced by an approximating gate, and one shows that every approximator is far from the target function. Razborov also showed that the method, in a natural general form, cannot prove more than linear lower bounds for…
Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-CompleteResearch Paper
Exact counting asks for the number of solutions rather than whether a solution exists. A tiling problem makes this distinction concrete: a region can admit tilings whose number is difficult to compute even when tileability has an efficient criterion. Restricting the pieces to one fixed family and the region to an ordinary square leaves only one varying…
Random-Order Online Facility Location Beyond Uniform Opening CostsResearch Paper
A facility-location decision trades a one-time setup cost against repeated travel or service costs. In the online facility-location problem, demand points arrive one at a time, and an arriving point must immediately receive service from a facility that has already opened. An expensive facility may be worthwhile for many nearby requests, but those future…
Deterministic Spectral Sparsification in Almost-Linear Time for Dense GraphsResearch Paper
A spectral sparsifier of a weighted graph G is a reweighted subgraph H with few edges whose Laplacian quadratic form approximates that of G for every vector. It preserves every cut approximately and also the linear-algebraic structure used by electrical flows, random walks and Laplacian solvers, so an algorithm whose cost grows with the number of edges can…