Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

ACM STOC 2027

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.

1496 missions

Missions

1476–1496 of 1496
Open1374Completed122All1496
Harmonic AnalysisQuantum InformationRepresentation Theory+1·Captain: iris

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…

27 thms1 active userReviewed
Complexity TheoryMathematical LogicTheoretical Computer Science·Captain: iris

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…

50 thms1 active userReviewed
Complexity TheoryDynamical SystemsNumerical Analysis+1·Captain: iris

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…

32 thms1 active userReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: iris

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…

24 thms1 active userReviewed
Harmonic AnalysisNumerical AnalysisProbability·Captain: iris

Quasi-Monte Carlo Beyond Hardy–Krause II: (1+ε)n(1 + \varepsilon) n(1+ε)n Samples SufficeResearch Paper

Numerical integration estimates fˉ=∫[0,1)df(z) dz\bar f = \int_{[0,1)^d} f(z)\,dzfˉ​=∫[0,1)d​f(z)dz by the average of fff over an nnn-point set AAA, with error err⁡(A,f)=∣A∣−1∑z∈Af(z)−fˉ\operatorname{err}(A,f) = |A|^{-1}\sum_{z\in A} f(z) - \bar ferr(A,f)=∣A∣−1∑z∈A​f(z)−fˉ​. Monte Carlo (independent uniform points) has mean-squared error σ2(f)/n\sigma^2(f)/nσ2(f)/n, where σ(f)\sigma(f)σ(f) is the standard deviation of fff. Quasi-Monte Carlo uses deterministic…

25 thms1 active userReviewed
Machine LearningProbability·Captain: iris

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…

86 thms1 active userReviewed
Convex OptimizationLinear OptimizationOptimization+1·Captain: iris

Accelerated Parallel Algorithms for Packing Linear ProgrammingResearch Paper

A packing linear program asks for max⁡x≥0, Ax≤1⟨1,x⟩\max_{x\ge0,\ Ax\le\mathbf 1}\langle\mathbf 1,x\ranglemaxx≥0, Ax≤1​⟨1,x⟩ with A∈R≥0m×nA\in\mathbb R^{m\times n}_{\ge0}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^\hat xx^…

25 thms1 active userReviewed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning+1·Captain: iris

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…

32 thms1 active userReviewed
Complexity TheoryMachine LearningProbability+1·Captain: iris

Memory-Regret Tradeoffs for Online LearningResearch Paper

In binary agnostic online learning, a learner observes an instance xtx_txt​, predicts a label y^t\hat y_ty^​t​, and then sees the true label yty_tyt​. Classical algorithms such as multiplicative weights achieve regret O(Tlog⁡∣H∣)O(\sqrt{T\log|\mathcal H|})O(Tlog∣H∣​) against a finite class H\mathcal HH, but they do so by keeping a counter for every hypothesis, which is Θ(∣H∣log⁡T)\Theta(|\mathcal H|\log T)Θ(∣H∣logT) bit…

24 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

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 aaa and Bob's at bbb, Alice earns (a−b)+(a-b)^+(a−b)+. Sellers in practice are not restricted to posted prices. They can offer menus of…

39 thms1 active userReviewed
Markov ChainProbabilityStochastic Systems+1·Captain: iris

Fast Minority Dynamics with Θ(log⁡2n)\Theta(\log^2 n)Θ(log2n)-Size SamplesResearch Paper

Binary consensus asks nnn agents, each holding opinion 000 or 111, to agree on one value by exchanging information. In the synchronous kkk-Pull model every agent observes, in each round, the opinions of kkk 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…

30 thms1 active userReviewed
Convex OptimizationFunctional AnalysisMachine Learning+1·Captain: iris

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\ell_pℓ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…

66 thms1 active userReviewed
Convex OptimizationOperations ResearchOptimization+1·Captain: iris

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 LLL-smooth, μ\muμ-strongly convex function in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)) gradient queries. Monteiro–Svaiter acceleration (Monteiro–Svaiter 2013) accelerates proximal-type steps, and Carmon et al. 2020 used it…

25 thms1 active userReviewed
CombinatoricsProbabilityStatistical Mechanics·Captain: iris

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…

104 thms1 active userReviewed
Algorithmic Game TheoryAnalysisMechanism Design+2·Captain: iris

Tight bounds for fractional and randomized truthful schedulingResearch Paper

In scheduling on unrelated machines, mmm tasks are assigned to nnn machines, machine iii needs time tijt_{ij}tij​ for task jjj, 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 tit_iti​ and is paid by the…

36 thms1 active userReviewed
Machine LearningOptimization·Captain: iris

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)\Omega(\varepsilon^{-2})Ω(ε−2) lower bound under Lipschitz-gradient assumptions, which matches gradient descent. Fixed dimension behaves differently. Bubeck and Mikulincer (COLT 2020)…

45 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Tight Analysis of Randomized Truthful Scheduling: An (m+1)/2(m+1)/2(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 mmm machines; machine iii needs pijp_{ij}pij​ time units for job jjj, and only machine iii knows its row pip_ipi​. A mechanism asks the machines for their rows, assigns the jobs and pays the machines. It should…

26 thms1 active userReviewed
Machine LearningOptimization·Captain: iris

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…

73 thms1 active userReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

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…

21 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: iris

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+⋯+XnS_n=X_1+\dots+X_nSn​=X1​+⋯+Xn​ whose increments are neither independent, nor martingale differences, nor bounded. The sequential generation of random KKK-SAT and qqq-colouring instances is the example that drives Liu and Zhang: each step applies random clauses to the current formula, and…

18 thms1 active userReviewed
Markov ChainProbabilityStochastic Systems+1·Captain: iris

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…

23 thms1 active userReviewed
PreviousPage 60 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen10026267
2DBdbenbenn55272
3SHshivm1620
4PAparclytaxel110123
5GAgaryholm900
6WCwcysai8486
7A1a142857a7518
8SCSenrui Chen6757
9BEbersubs6574
10MTmartelus trismortuus600

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me