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.

1353 open missions

Missions

1026–1050 of 1353
Open1353Completed146All1499
Linear OptimizationOptimization·Captain: iris

An Ω(N)\Omega(\sqrt{N})Ω(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 NNN inequality constraints, the classical analysis (Renegar 1988) reduces the duality gap by a constant factor every O(N)O(\sqrt N)O(N​) iterations. Practical solvers need far fewer…

33 thms2 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: iris

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 MMM 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)(2-1/M)(2−1/M)-competitive for it on identical machines (Graham 1966)…

25 thms2 active usersReviewed
Markov ChainMathematical PhysicsProbability+1·Captain: iris

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤12+\eps\beta \le \tfrac{1}{2} + \epsβ≤21​+\epsResearch Paper

The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: nnn 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…

38 thms2 active usersReviewed
Complexity TheoryConvex OptimizationOptimization+1·Captain: iris

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⊆RnK\subseteq\mathbb R^nK⊆Rn, given radii with B2(0,r)⊆K⊆B2(0,R)B_2(0,r)\subseteq K\subseteq B_2(0,R)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…

74 thms2 active usersReviewed
Markov ChainMathematical PhysicsProbability+1·Captain: iris

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 Δ\DeltaΔ the parameter …

26 thms2 active usersReviewed
Graph TheoryMarkov ChainProbability+1·Captain: iris

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…

30 thms2 active usersReviewed
Markov ChainMathematical PhysicsProbability+1·Captain: iris

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: nnn 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…

32 thms2 active usersReviewed
CombinatoricsOptimizationTheoretical Computer Science·Captain: iris

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…

42 thms2 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: iris

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 xtx_txt​ and receives the value f(xt)f(x_t)f(xt​) and a subgradient gtg_tgt​. Its oracle complexity is the error it can guarantee after TTT queries, uniformly over a class of functions. When the feasible set is the unit ball of a norm ∥⋅∥p\|\cdot\|_p∥⋅∥p​ an…

55 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: iris

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…

15 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: iris

Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared RandomnessResearch Paper

Consider mmm devices sharing KKK 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…

43 thms2 active usersReviewed
Markov ChainQuantum Error CorrectionQuantum Information·Captain: iris

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…

51 thms2 active usersReviewed
Convex OptimizationOptimization·Captain: iris

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…

52 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization+1·Captain: iris

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…

23 thms2 active usersReviewed
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 thms2 active usersReviewed
Markov ChainMathematical PhysicsProbability·Captain: iris

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 NNN 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≤β<10\le\beta<10≤β<1 has been a central…

23 thms2 active usersReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: iris

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…

16 thms1 active userReviewed
Information TheoryProbabilityReinforcement Learning+1·Captain: iris

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+γ∑iwaimax⁡h≤KiQi(h)t_a(Q)=r_a+\gamma\sum_i w_{ai}\max_{h\le K_i}Q_i(h)ta​(Q)=ra​+γ∑i​wai​maxh≤Ki​​Qi​(h) with 0<γ<10<\gamma<10<γ<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…

37 thms1 active userReviewed
CombinatoricscryptographyTheoretical Computer Science·Captain: mikedeng1

Optimal Subcubic Byzantine Agreement with Plain PKIResearch Paper

Byzantine agreement (BA) asks nnn parties, up to ttt 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/3t<n/3t<n/3 (Pease–Shostak–Lamport 1980). With a public-key infrastructure (PKI), where every party can sign…

23 thms1 active userReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

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 nnn tokens, leave-one-out attribution records the measurement after deleting each token individually. Direct evaluation takes nnn model calls. Liaw, Mehta, Velegkas and Zhou study when all these values can be estimated with fewer calls,…

20 thms1 active userReviewed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

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 HHH, and an optimal policy that depends only on the current state and time is found by dynamic programming.

20 thms1 active userReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Fast Quantum Byzantine Agreement with Nearly Linear Quantum CommunicationResearch Paper

In Byzantine agreement, nnn processes with input bits must decide a common bit although up to ttt 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…

22 thms1 active userReviewed
Complexity TheoryInformation TheoryQuantum Information+1·Captain: iris

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))K(x,y)=K(x)+K(y\mid x)\pm O(\log(|x|+|y|+2))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…

22 thms1 active userReviewed
Convex OptimizationMachine LearningOptimization+2·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓ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>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
Complexity TheoryMachine LearningMathematical Logic+1·Captain: Shuze Chen

A Witnessing Duality for ReLU Network DepthResearch Paper

How many hidden layers a ReLU network needs to compute max⁡(x1,…,xn)\max(x_1,\dots,x_n)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…

7 thms1 active userReviewed
PreviousPage 42 of 55Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn691113
3SHshivm1630
4PAparclytaxel150172
5MTmartelus trismortuus1050
6GAgaryholm900
7WCwcysai8486
8A1a142857a7518
9SCSenrui Chen6757
10BEbersubs6574

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