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.
Quantum Lazy Sampling and Path Recording for Any GroupResearch Paper
Many arguments in quantum cryptography and query complexity analyse an algorithm that queries a unitary drawn at random from a group: a Haar-random unitary, a random permutation matrix, a random diagonal phase, a random orthogonal matrix. Classically such arguments use lazy sampling: a random function is never fixed in advance, its values are drawn when…
Unique Optimality with Polynomially Bounded ScoresResearch Paper
USAT asks whether a Boolean formula has exactly one satisfying assignment; it is complete for the class US of languages accepted by nondeterministic polynomial-time machines with exactly one accepting computation (Blass–Gurevich, Information and Control 1982; Valiant–Vazirani 1986). Optimization raises a different uniqueness question: is the optimal solution…
One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for PTIME and PSPACEResearch Paper
Ordinary differential equations with polynomial right-hand sides are a model of analog computation: chemical reaction networks, the General Purpose Analog Computer and continuous-time recurrent networks all reduce to them. Since Graça, Campagnolo and Buescu (2008) and Bournez, Graça and Pouly (2017) it is known that polynomial ODEs simulate Turing machines…
Weighted Set Cover with Constant Worst-Case Recourse: From Exponential to Best-Known Update TimeResearch Paper
In fully dynamic weighted set cover, a fixed family of sets with positive costs is given once, and elements of the universe are then inserted into and deleted from an active set. After every update an algorithm must hold a subfamily that covers the active elements at nearly minimum cost. Besides the approximation ratio, two resources are measured per…
Quasi-Monte Carlo Beyond Hardy–Krause II: (1+ε)n Samples SufficeResearch Paper
Numerical integration estimates fˉ=∫[0,1)df(z)dz by the average of f over an n-point set A, with error err(A,f)=∣A∣−1∑z∈Af(z)−fˉ. Monte Carlo (independent uniform points) has mean-squared error σ2(f)/n, where σ(f) is the standard deviation of f. Quasi-Monte Carlo uses deterministic…
Replicable Online Learners Must Gamble: The Typical-Case Price of ReplicabilityResearch Paper
A randomized algorithm is replicable if, run twice with the same internal randomness on two independent samples from the same distribution, it returns the same output with high probability. Impagliazzo, Lei, Pitassi and Sorrell introduced the notion for batch learning (ILPS22), where it is now known to be equivalent to approximate differential privacy up to…
Accelerated Parallel Algorithms for Packing Linear ProgrammingResearch Paper
A packing linear program asks for maxx≥0,Ax≤1⟨1,x⟩ with A∈R≥0m×n. Packing LPs model resource allocation, fractional matching and fractional knapsack, and they are subroutines in approximation algorithms for scheduling and combinatorial auctions. The standard goal is low accuracy: a feasible x^…
Optimal Regret for Profit Maximization in Bilateral TradeResearch Paper
In bilateral trade, a seller and a buyer with private valuations meet an intermediary who posts a purchase price to the seller and a sale price to the buyer. Trade happens only if both accept, and the intermediary keeps the difference. The Myerson–Satterthwaite impossibility theorem makes this setting a central one in mechanism design, and its online…
Memory-Regret Tradeoffs for Online LearningResearch Paper
In binary agnostic online learning, a learner observes an instance xt, predicts a label y^t, and then sees the true label yt. Classical algorithms such as multiplicative weights achieve regret O(Tlog∣H∣) against a finite class H, but they do so by keeping a counter for every hypothesis, which is Θ(∣H∣logT) bit…
On Competing Sellers with Substitutable GoodsResearch Paper
When two sellers offer substitutable goods to the same buyer, classical Bertrand competition with posted prices drives the weaker seller's revenue to zero and leaves the stronger one only the value gap: if the buyer values Alice's good at a and Bob's at b, Alice earns (a−b)+. Sellers in practice are not restricted to posted prices. They can offer menus of…
Fast Minority Dynamics with Θ(log2n)-Size SamplesResearch Paper
Binary consensus asks n agents, each holding opinion 0 or 1, to agree on one value by exchanging information. In the synchronous k-Pull model every agent observes, in each round, the opinions of k agents chosen independently and uniformly at random, and updates its opinion by a fixed local rule. For the MAJORITY rule, where an agent adopts the majority of…
When Do Gradients Suffice? A Characterization of First-Order Convex OptimizationResearch Paper
First-order methods (gradient descent, Mirror Descent, their stochastic and accelerated variants) are the default tools of large-scale convex optimization, and their guarantees are usually stated in a Euclidean or ℓp geometry. A basic question underlies all of them: in which normed spaces can a convex Lipschitz function on the unit ball be minimized to…
Universal Acceleration: New Approaches to Heavy Ball DiscretizationResearch Paper
Two accelerated methods sit at the centre of first-order convex optimization. Nesterov's accelerated gradient descent (Nesterov 1983) minimizes an L-smooth, μ-strongly convex function in O(L/μlog(1/ε)) gradient queries. Monteiro–Svaiter acceleration (Monteiro–Svaiter 2013) accelerates proximal-type steps, and Carmon et al. 2020 used it…
Spatial sorting and the geometry of lattice spin systems at fixed magnetizationResearch Paper
Programmable matter and self-organizing particle systems ask a population of simple agents with a fixed inventory to sort itself into regions by type. A standard way to analyse such algorithms is to model the configurations with a spin system and to run a Markov chain whose stationary law is its Gibbs distribution. Conservation of particles then becomes a…
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…
Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower BoundsResearch Paper
Finding a point where the gradient of a smooth nonconvex function is small is the basic task of nonconvex optimization. In sufficiently high dimension, Carmon et al. proved an Ω(ε−2) lower bound under Lipschitz-gradient assumptions, which matches gradient descent. Fixed dimension behaves differently. Bubeck and Mikulincer (COLT 2020)…
Tight Analysis of Randomized Truthful Scheduling: An (m+1)/2 Lower BoundResearch Paper
Truthful scheduling on unrelated machines is the problem with which Nisan and Ronen started algorithmic mechanism design (NR99). A set of jobs has to be assigned to m machines; machine i needs pij time units for job j, and only machine i knows its row pi. A mechanism asks the machines for their rows, assigns the jobs and pays the machines. It should…
0.4633-Approximation for Online and Offline Non-Monotone DR-Submodular MaximizationResearch Paper
Maximizing a nonnegative DR-submodular function over a down-closed convex set is the continuous counterpart of non-monotone submodular set-function maximization. It appears in MAP inference for determinantal point processes, revenue maximization, and the continuous relaxations used to round set-function problems. In the online version, an adversary chooses…
Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit FeedbackResearch Paper
Many sequential decisions under uncertainty share one shape: a decision maker inspects random quantities one at a time, decides after each inspection what to inspect next or whether to stop, and collects a reward that depends on what was seen. Stochastic Boolean function evaluation, the secretary problem, optimal stopping, Pandora's box, scheduling and…
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…
Minority Dynamics with Small SamplesResearch Paper
Consensus and bit dissemination are basic tasks for populations of simple agents that interact through random samples: biological collectives, chemical reaction networks and gossip protocols in distributed systems. In consensus, a population holding two opinions must come to agree on one of them. In bit dissemination, one or more sources hold a fixed…