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.

1374 open missions

Missions

376–400 of 1374
Open1374Completed122All1496
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Money Burning Mechanism Design: From Welfare to SurplusResearch Paper

Waiting time and effort can screen people for access to a service, but their costs do not become revenue available to someone else. In such settings, the value of the selected outcome alone misses part of the social cost. The relevant objective is residual surplus: the agents' total value minus the payments they incur. A mechanism can improve its allocation…

16 thms3 active usersReviewed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Algorithmic List Decoding of Reed–Solomon Codes up to CapacityResearch Paper

A Reed–Solomon code of length nnn and dimension kkk over a finite field Fq\mathbb F_qFq​ encodes a message polynomial PPP of degree less than kkk as its evaluations (P(α1),…,P(αn))(P(\alpha_1),\dots,P(\alpha_n))(P(α1​),…,P(αn​)) at distinct points. These codes are used throughout storage, communication and cryptography, and they are the basic object of algebraic coding theory. In list decoding the…

27 thms3 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid BasesResearch Paper

A matroid describes a finite family of feasible subsets closed under taking subsets, with an exchange property that makes all maximal feasible subsets have the same size. Those maximal subsets are its bases. Spanning trees of a connected graph give one familiar example. A real cost on each element induces an additive cost on each base. Adding a constraint…

15 thms3 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

Sorting from CounterexamplesResearch Paper

Ranking systems (search, recommendation, matching) present a user with a complete ordered list, and the most natural correction a user can give is local: "these two items are in the wrong order". Empirical studies of preference elicitation, cited by the paper as Carterette, Bennett, Chickering and Dumais (2008) and Schnabel et al. (2014), report that such…

13 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Directed Global Minimum Cut in Almost-Linear TimeResearch Paper

A directed global minimum cut measures how cheaply a directed network can lose reachability: remove a set of arcs of minimum total weight so that some vertex can no longer reach another. Direction matters because losing access in one direction need not affect access in the reverse direction. The optimization problem concerns the weakest ordered-pair…

21 thms3 active usersReviewed
AlgebraInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity GapsResearch Paper

An error-correcting code adds redundancy so that a message can still be recovered after some transmitted symbols change. Reed–Solomon codes use evaluations of a polynomial over a finite field. Their algebraic definition makes it possible to ask precise questions about how many corrupted symbols an algorithm can tolerate. When unique recovery is impossible, l…

17 thms3 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Fair Share Allocations for Almost All AgentsResearch Paper

Allocating indivisible goods creates a conflict between an agent's individual fairness benchmark and the requirement that different agents receive disjoint bundles. With divisible goods, a proportional allocation can give each agent her entitlement fraction of every good. Indivisibility removes that option. A benchmark must account for the sizes and values…

31 thms3 active usersReviewed
AlgebraComplexity TheoryLinear algebra·Captain: mikedeng1

Approximating commutative rank of matrix spaces in NCResearch Paper

A collection of rational matrices describes many possible matrices: any rational linear combination of the given matrices is allowed. A basic algorithmic question asks for a combination whose rank is as large as possible. This question includes algebraic formulations of matching and related combinatorial optimization problems. An approximation should return…

33 thms3 active usersReviewed
Information TheoryProbabilityStatistics·Captain: mikedeng1

Settling the Sample Complexity of Rényi Entropy EstimationResearch Paper

Entropy estimation asks how much data is needed to measure the randomness of an unknown probability distribution. The distribution itself need not be recovered: an estimator receives samples and reports one real number. This distinction matters on a large alphabet, where many symbols may remain unseen. Rényi entropy supplies a family of such measurements,…

18 thms3 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Fixed-Parameter Algorithm for 4-Block Integer ProgrammingResearch Paper

Many integer optimization models describe small local decisions connected through shared resource constraints. A 4-block integer program also allows a small vector of global decisions to enter every local system. Scheduling, transportation, production planning and stochastic network models motivate these structures; the pinned submission discusses these…

31 thms3 active usersReviewed
Information TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Linear Set Reconciliation with O(d)O(d)O(d) Additive RedundancyResearch Paper

Two parties each hold a set of elements from a universe of size nnn, and the sets differ in at most ddd elements. If one party sends a short message that is a binary linear function of its set, the other can cancel the common elements and recover the difference. This is set reconciliation, and it reduces to binary sparse recovery: recover a vector …

30 thms3 active usersReviewed
Algorithmic Game TheoryComputational ComplexityLinear Optimization·Captain: mikedeng1

Designing Information in a Forest: Algorithmic AspectsResearch Paper

An informed sender can influence several decision makers by choosing what to reveal about a common unknown state. When some decision makers observe messages addressed to others, an information policy must account for those observations. A policy designed for independent private messages may have a different effect once the messages become visible elsewhere.…

14 thms3 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree GraphsResearch Paper

A multi-spin system assigns one of finitely many spins to each vertex of a graph. Each assignment receives a weight determined by local vertex preferences and interactions across edges. The sum of these weights, the partition function, is useful both as a counting quantity and as the normalizing constant of a probability distribution. Computing this sum…

25 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal Tolerant Testing of Lindbladian DissipationResearch Paper

A quantum device can change because of coherent Hamiltonian motion or because of coupling to its environment. Distinguishing these contributions matters when assessing whether physical noise lies below a prescribed tolerance. Reconstructing every interaction would answer a substantially larger question than such a test requires. Bao, Cai and Shang study the…

21 thms3 active usersReviewed
Computational ComplexityGraph TheoryInformation Theory·Captain: mikedeng1

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent SetResearch Paper

A graph stream presents the edges of a graph one at a time while an algorithm keeps a limited working memory. Maximum Clique asks for a largest set of vertices with every pair joined by an edge. Streaming algorithms for this problem are relevant to the study of what graph information can be retained in a small memory: the desired output is a set of…

22 thms3 active usersReviewed
CombinatoricsQuantum InformationRepresentation Theory·Captain: mikedeng1

Optimal cloning of mixed statesResearch Paper

The no-cloning theorem rules out a device that reproduces every unknown quantum state exactly. Experiments and algorithms instead operate with nonzero error, so a quantitative question remains: how many identical input copies are needed to produce additional copies while keeping the entire output close to the desired product state? The distinction between…

26 thms3 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

Ruling out Fast Approximation Algorithms for Clique, Biclique, Collinearity, and Arithmetic ProgressionsResearch Paper

A clique is a collection of vertices in a graph with an edge between every pair. Detecting a fixed small clique is a basic graph algorithm problem. A natural approximation question asks whether a promise of a much larger clique helps detect a smaller one. In particular, could a program distinguish a graph containing a large fixed clique from a graph…

25 thms3 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

Arc Kayles is PSPACE-completeResearch Paper

Arc Kayles is a two-player game on a finite undirected graph. The players alternate, and a move picks an edge uvuvuv of the current graph and deletes both endpoints. Under normal play the first player without a legal move loses. The winner is the player who plays the last edge of a maximal matching of the original graph, so Arc Kayles is to maximal matchings…

19 thms3 active usersReviewed
Quantum InformationQuantum Mechanics·Captain: mikedeng1

Sharp universal death of entanglement threshold for Pauli HamiltoniansResearch Paper

A quantum system in thermal equilibrium can retain correlations that cannot be reproduced by mixing independently prepared single-qubit states. For researchers studying quantum many-body systems and classical descriptions of quantum states, a basic question is when sufficiently high temperature rules out this entanglement uniformly over an interaction…

18 thms3 active usersReviewed
Computational ComplexityProbabilityQuantum Information·Captain: mikedeng1

BQP⊆IP Does Not RelativizeResearch Paper

A quantum computation can produce an answer that a classical computer cannot efficiently reproduce. An interactive proof asks whether a classical verifier can nevertheless check that answer by exchanging messages with an unrestricted prover. The verifier must accept correct claims with high probability and reject incorrect claims regardless of the prover’s…

25 thms3 active usersReviewed
Graph TheoryOptimizationProbability·Captain: mikedeng1

Optimal Sample Complexity for Max-CutResearch Paper

A maximum cut partitions a graph's vertices into two parts to maximize the total weight of edges between them. When a graph is too large to inspect in full, estimating this optimum from a small sample can reduce the amount of graph data needed. A value coreset is a small reweighted graph whose maximum-cut value approximates the original value. Returning a…

34 thms3 active usersReviewed
cryptographyNumber Theory·Captain: mikedeng1

A New Approach to Reducing Modulus Requirements in Homomorphic Computation: Precision Allocation in CKKSResearch Paper

CKKS is a homomorphic encryption scheme for approximate arithmetic on real and complex numbers. A single ciphertext carries several independent values, called slots, with a common scale controlling the size of numerical errors relative to messages. This representation makes unequal accuracy requirements relevant: a computation may need many accurate bits in…

11 thms3 active usersReviewed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Improved Impossibility Bounds for Maximin Share AllocationsResearch Paper

Dividing indivisible goods among agents with additive valuations is a central problem of fair division, and the maximin share (MMS) is its most studied fairness benchmark: an agent's MMS is the value she can guarantee herself by partitioning all goods into nnn bundles and receiving the worst one. Kurokawa, Procaccia and Wang showed that an allocation giving…

21 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depthResearch Paper

Random circuit sampling asks for samples from the bitstring distribution produced by a given quantum circuit acting on the all-zero input. Analyses of this task and its experimental benchmarks use statistical predictions about random circuits. A central prediction concerns how the probability of one fixed output varies when the circuit is sampled…

18 thms3 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Last-Iterate Stationarity of Muon with Finitely Many Newton-Schulz IterationsResearch Paper

Muon is an optimizer for matrix-shaped parameters in neural-network training. At each step it forms a momentum average of stochastic gradients and replaces that matrix by an approximately orthogonalized version before taking a step. In practice the orthogonalization is not the exact polar factor. It is a fixed small number JJJ (commonly J=5J=5J=5) of quintic Newton–…

18 thms3 active usersReviewed
PreviousPage 16 of 55Next

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