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.

178 completed missions

Missions

76–100 of 178
Open1321Completed178All1499
🏆Completed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Explicit Edit Codes via MulticoloringResearch Paper

An edit channel can insert a symbol, delete a symbol, or substitute one symbol for another. Insertions and deletions change the positions of subsequent symbols, so a decoder must recover information without knowing which received positions correspond to transmitted positions. A code restricts transmitted words so that these changes can be corrected. The…

53 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

The Harmonic Online k-Server Algorithm Is Poly(k)-CompetitiveResearch Paper

The online k-server problem concerns mobile servers that must answer requests without knowing future requests. Moving a server costs the distance it travels. A decision rule can achieve a strong comparison with other service schedules while still requiring substantial computation or memory to make each decision. Harmonic addresses the computational side…

21 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: mikedeng1

Robustly Obedient Data Driven Persuasion under State-dependent Sender PayoffsResearch Paper

In Bayesian persuasion (Kamenica and Gentzkow, 2011, https://doi.org/10.1257/aer.101.6.2590), a Sender commits to a signaling policy that maps the state of the world to recommendations, and a Receiver who knows the prior updates on the recommendation and acts. The standard analysis assumes the Sender knows the prior. In many applications the Sender instead…

8 thms3 active usersReviewed
🏆Completed
AlgebraCombinatorics·Captain: mikedeng1

Optimal partition rank bounds for the determinant and other multilinear polynomialsResearch Paper

A polynomial can be represented as a sum of products in many ways. When its variables are divided into rows and every monomial uses exactly one variable from each row, a product can separate some rows from the others. The least number of such products is its partition rank. This measure studies a restricted form of algebraic computation: the factors in one…

52 thms3 active usersReviewed
🏆Completed
AlgebraComplexity Theory·Captain: mikedeng1

Hitting sets From Derivations: Waring Rank and Noncommutative ABPsResearch Paper

Polynomial identity testing asks whether a polynomial presented by a computation is identically zero. In its blackbox form, only evaluations of that computation are available. A hitting set for a class of polynomials is a fixed finite set of evaluation points on which every nonzero member has a nonzero value. Such a set turns identity testing for that class…

20 thms3 active usersReviewed
🏆Completed
cryptographyQuantum Information·Captain: mikedeng1

Unconditional Unclonable EncryptionResearch Paper

Unclonable encryption asks whether one quantum ciphertext can be split into two systems that both retain useful information about its plaintext. The secret key is hidden during the split and then revealed to both recipients, who must answer without communicating. Cryptographers studying this question need a guarantee about every possible split, including a…

34 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCsResearch Paper

In an edge-colored graph, a rainbow cycle is a cycle on which no color occurs twice. Extremal graph theory asks how much average degree forces such a cycle. The properly colored case already connects this question to bounds for locally correctable codes. Lin's submission extends the graph theorem to nonnegative edge weights and edges bearing several colors…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Stability Dichotomies for Boolean Constraint Satisfaction ProblemsResearch Paper

A solver can return a correct answer and still react sharply to a small change in its input. For a constraint satisfaction problem, deleting a requirement leaves every old solution valid, but a solver may nevertheless change many variable values. Understanding when that disruption is unavoidable is useful for distinguishing a property of the problem from a…

18 thms3 active usersReviewed
🏆Completed
Complexity TheoryQuantum Information·Captain: mikedeng1

QMA has perfect completenessResearch Paper

In a Merlin–Arthur proof system, an all-powerful prover sends a proof to an efficient verifier, who accepts or rejects an input. QMA is the version in which the proof is a polynomial-size quantum state and the verifier is an efficient quantum circuit. A system has perfect completeness if every YES instance admits a proof accepted with probability exactly…

53 thms3 active usersReviewed
🏆Completed
OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

The Optimizer's Windfall: Bounding Hindsight Gain under Random RestrictionsResearch Paper

Sampling variables is a basic way to estimate large optimization problems. An algorithm reads the interactions among the retained variables, optimizes that smaller instance, and rescales the answer. Every fixed assignment has the right expected score after rescaling. The assignment chosen after seeing the sample can do better, however, because it responds…

33 thms3 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?Research Paper

Routing models compare what individual users prefer with the total delay experienced by all users. Exact optimization of a user's route is a strong behavioral requirement: users may accept alternatives whose delay is only slightly worse than the best available. The resulting relaxation raises a quantitative question even when demands, available routes, and…

18 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchProbability+1·Captain: mikedeng1

Low-Rank Denoising for Predict-then-OptimizeResearch Paper

A predict-then-optimize pipeline estimates unknown costs and passes the estimate to an optimizer. In shortest-path problems, edge costs can come from noisy measurements or simulation replications. Averaging more replications reduces noise, but costs across different instances may also share structure: several edges can vary together. A projection estimator k…

6 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

The Greedy Superstring Conjecture Is FalseResearch Paper

The shortest common superstring problem asks for a shortest word containing every member of a finite input set as a contiguous block. It models the compression of overlapping records and an idealized version of sequence assembly. A natural algorithm repeatedly joins the two current words with the longest suffix-prefix overlap. Understanding how much length…

21 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed GraphsResearch Paper

The restricted shortest paths problem asks for a route that is short while respecting a separate cost budget. Travel time and monetary cost need not favor the same route. The same distinction appears in quality-of-service routing, where delay is optimized subject to another resource constraint. Ashvinkumar discusses these applications and the difficulty of…

16 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Is Randomness Necessary for Adaptive Data Analysis?Research Paper

A dataset is often reused to answer questions chosen after seeing earlier answers. Each answer can influence the next question, so the usual guarantee for one question fixed in advance does not automatically extend to the resulting interaction. Adaptive data analysis asks what a mechanism can reliably reveal about a population from a single finite sample in…

14 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Quantitative Results on Super-Ramanujan GraphsResearch Paper

A ddd-regular graph always has ddd as its largest adjacency eigenvalue. How far the remaining eigenvalues stay from ddd measures how well the graph expands, and good spectral expanders are used throughout pseudorandomness, error-correcting codes, derandomization and the design of communication networks. The Alon–Boppana bound shows that for a fixed degree ddd the…

20 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: mikedeng1

Ramsey Obstructions to DisambiguationResearch Paper

A partial binary classifier may leave a point unlabeled. For a separating hyperplane with a prescribed margin, this represents points too close to the boundary to receive a prescribed label. A class of such classifiers can have bounded VC-dimension, even when the ambient Euclidean dimension grows. Completing all missing labels asks whether this simplicity…

30 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Cutting a Cake For Human Consumption: An Elementary nnn-agent Cake Cutting ProtocolResearch Paper

Envy-free cake cutting asks how to divide a divisible resource among nnn agents with different preferences so that no agent prefers another agent's share to her own. It is one of the founding problems of fair division, and its query complexity is a standard benchmark for the theory of fair-division protocols.

65 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryRandom Matrix Theory·Captain: mikedeng1

The Sharp Dimension Bound in the Johnson–Lindenstrauss LemmaResearch Paper

A collection of vectors is often used through the distances between its elements. Reducing the number of coordinates is useful only if those distances remain reliable. Euclidean dimension reduction asks how small the target dimension can be when every pairwise distance must be preserved to a specified relative accuracy. The question is relevant to metric…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Linear Max Load and Additive StructureResearch Paper

A hash function compresses a large universe into a small number of bins, and its quality is judged by how evenly it spreads a set of inputs. For a set SSS of nnn items hashed into nnn bins by a fully random function, the expected size of the fullest bin, the expected max load, is (1+o(1))ln⁡n/ln⁡ln⁡n(1+o(1))\ln n/\ln\ln n(1+o(1))lnn/lnlnn. Fully random functions are expensive in time, space and…

28 thms3 active usersReviewed
🏆Completed
Functional AnalysisLinear algebraQuantum Information·Captain: iris

From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative DecodingResearch Paper

Decoded quantum interferometry (DQI) and its Hamiltonian variant (HDQI) prepare quantum states whose amplitudes are a polynomial of a target problem: a polynomial of a code's parity checks, or a polynomial p(HB)p(H_B)p(HB​) of a Hamiltonian HBH_BHB​. Such states are used to bias measurements toward high-scoring or low-energy sectors, and their preparation rests on a…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Optimal universal sets for submodular functionsResearch Paper

A set function f:2[n]→Rf:2^{[n]}\to\mathbb Rf:2[n]→R is submodular if f(S∪T)+f(S∩T)≤f(S)+f(T)f(S\cup T)+f(S\cap T)\le f(S)+f(T)f(S∪T)+f(S∩T)≤f(S)+f(T) for all S,T⊆[n]S,T\subseteq[n]S,T⊆[n]. Cut functions of graphs and digraphs, coverage functions, entropy of subsets of random variables and many utility functions in economics are submodular. Maximizing a nonnegative submodular function with no constraint generalizes Max-Cut and…

18 thms3 active usersReviewed
🏆Completed
Group TheoryMachine LearningRepresentation Theory·Captain: iris

The State Complexity of Block-Diagonal State Space ModelsResearch Paper

Given a sequence x1,…,xTx_1,\dots,x_Tx1​,…,xT​ of elements of a fixed finite group GGG, a state-tracking model must report the running product xT⋯x1x_T\cdots x_1xT​⋯x1​ after every prefix. The task tests structured memory: the model has to preserve order, retain information for arbitrary sequence lengths, and implement the multiplication law. It also has complexity-theoretic content,…

26 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsMechanism Design+1·Captain: iris

Fair Team ContractsResearch Paper

A firm, a research group or an open-source project often pays a team for a joint outcome it cannot observe in detail: it sees whether the project succeeded, not who worked. Combinatorial contract theory models this as a principal who offers each hired agent a linear contract, a share of the success reward, and lets the agents decide whether to exert costly…

28 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: iris

Single-or-Sample: Online Fair Allocation for Combinatorial AgentsResearch Paper

Consider a relief center that hands out indivisible supplies to people arriving over time, each with different needs. Everything handed out is gone, and nothing is known about who comes next. Maximin share (MMS) fairness, introduced by Budish 2011, measures an agent's share using only that agent's own valuation: the value the agent could guarantee by…

32 thms3 active usersReviewed
PreviousPage 4 of 8Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin140143
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8BOBoomShaKaLaaaKa93100
9GAgaryholm900
10WCwcysai8486

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