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

51–75 of 178
Open1321Completed178All1499
🏆Completed
CombinatoricsMachine LearningProbability+1·Captain: Shuze Chen

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper

In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra+1·Captain: Shuze Chen

A Sharp Rigidity Law for Effective ResistanceResearch Paper

Effective resistances summarize a weighted graph as an electrical network: the resistance RuvR_{uv}Ruv​ between two vertices is the voltage needed to send one unit of current from uuu to vvv. They govern commute times and are the sampling probabilities of spectral sparsification (Spielman–Srivastava 2011), and they form a metric on the vertices.

10 thms3 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Adaptivity Gaps for Welfare-Maximizing Pooled TestingResearch Paper

Pooled screening uses a limited number of assays to clear potentially valuable individuals or resources. A negative test certifies every member of its pool as healthy. With a fixed budget, later tests can respond to earlier outcomes, directing the remaining resources toward different people after positive and negative results. The mathematical question is…

17 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

Robust Shattering ArgumentsResearch Paper

Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set BBB of unresolved nodes, and the analysis has to show that…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: Shuze Chen

A Better-than-2 Approximation for k-MedianResearch Paper

In uncapacitated facility location (UFL) one opens a set of facilities, each at a cost, and connects every client to its nearest open facility. In k-median one opens at most kkk facilities and pays only connection costs. The two problems are linked by a Lagrangian relaxation: replacing the constraint ∣S∣≤k|S|\le k∣S∣≤k by a penalty f⋅∣S∣f\cdot|S|f⋅∣S∣ turns k-median into UFL…

25 thms3 active users
🏆Completed
AlgebraComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

PIT and Reconstruction for Sums of High PowersResearch Paper

Polynomial identity testing (PIT) asks whether a polynomial given by an arithmetic circuit is identically zero. In the black-box version the algorithm may only evaluate the polynomial at points of its choice, and a deterministic black-box algorithm is the same thing as a hitting set: a fixed finite set of points at which every nonzero polynomial of the…

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

Draw, Then Draw: The Metric Distortion of Random-Size Stable LotteriesResearch Paper

A voting rule often receives rankings even when the quality of its decision depends on numerical costs. In metric social choice, voters and candidates occupy a common distance space. Each voter ranks closer candidates ahead of farther candidates, but the rule sees only those rankings. Its task is to choose a candidate, possibly at random, whose average…

63 thms3 active usersReviewed
🏆Completed
Formal VerificationGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Büchi Determinization with Optimal States and Square Root Index ImprovementResearch Paper

Automata on infinite words describe behavior that continues indefinitely. In formal verification, a system execution is such a word, and an acceptance condition expresses a property of its long-term behavior. Converting a nondeterministic automaton to a deterministic one can make subsequent operations possible, but the conversion has two costs: the number…

31 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

A (4m - 5)-Competitive Deterministic Algorithm for Online TransportationResearch Paper

An online transportation problem asks how to allocate arriving demand when destinations have fixed capacities and future demand is unknown. Cars arrive one at a time at points of a known finite metric space. Each car must immediately receive a garage with an unused slot. That assignment is irrevocable. The objective is the sum of the distances from arrival…

16 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: Shuze Chen

Sample Complexity of Multiclass OmnipredictionResearch Paper

Omniprediction, introduced by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389), asks for one predictor that serves every downstream decision maker at once. Each decision maker has their own loss, best-responds to the predicted label distribution, and should do as well as the best benchmark in a fixed class FFF. For binary labels, randomized…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: Shuze Chen

Fatness and FlatnessResearch Paper

The theory of sparsity of Nešetřil and Ossona de Mendez describes the algorithmically useful structure of sparse graph classes. Its central notion, nowhere denseness, has many equivalent definitions. Two of them matter here. The first says that, for every radius rrr, contracting disjoint connected subgraphs of radius at most rrr cannot produce arbitrarily large…

20 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability+1·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Algebraic GeometryCombinatorics·Captain: mikedeng1

Toward Algebraic Geometry of Fixed-Parameter Tractability: Case StudiesResearch Paper

A hitting set selects vertices so that every input hyperedge contains a selected vertex. In the parameterized problem, the question is whether a hitting set of size at most a given number kkk exists. Even when a small solution exists, the collection of feasible solutions can be large. For algorithms that retain possible certificates, the relevant question is…

11 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Polynomial Lower Bounds for Steiner Shortcuts via Test FunctionsResearch Paper

A directed reachability query asks whether a directed graph contains a path from one specified vertex to another. Many algorithms first add edges to reduce the number of edges that such a path needs. This matters in parallel and distributed computation because a path requiring many successive steps can force many rounds of communication or dependent work.…

24 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
🏆Completed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

Anticoncentration of the Permanent in Ginibre EnsemblesResearch Paper

The permanent of an n×nn\times nn×n matrix, per⁡A=∑σ∈Sna1σ(1)⋯anσ(n)\operatorname{per}A=\sum_{\sigma\in S_n}a_{1\sigma(1)}\cdots a_{n\sigma(n)}perA=∑σ∈Sn​​a1σ(1)​⋯anσ(n)​, is the determinant without signs. Computing it exactly is #P-hard, and its behaviour on random Gaussian matrices sits at the centre of the complexity-theoretic case for quantum advantage in BosonSampling. Aaronson and Arkhipov (AA13) reduced…

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

The Local Query Complexity of Greedy Coloring and Other Extendable Labeling ProblemsResearch Paper

A graph may be too large for an application to construct and store a complete solution before answering its first question. A local computation algorithm instead answers questions about individual vertices through queries to the underlying graph. Its answers must remain consistent with one solution of the whole graph. The relevant resource here is the…

23 thms3 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

A Width Hierarchy of Monotone Algebraic Branching ProgramsResearch Paper

Algebraic complexity studies how much arithmetic is needed to produce a polynomial from its variables and constants. A monotone computation uses only nonnegative coefficients, so terms cannot disappear by cancellation. This restriction makes resource lower bounds accessible while retaining models that distinguish addition, multiplication, and reuse of…

22 thms3 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov BoundResearch Paper

An insertion or deletion changes the positions of later symbols. A receiver therefore faces uncertainty about alignment as well as about the values of damaged bits. Edit-correcting codes address this problem by restricting the transmitted words so that nearby received sequences identify a unique original message. File synchronization is one concrete…

33 thms3 active usersReviewed
🏆Completed
Graph TheoryNumerical Analysis·Captain: mikedeng1

Nearly optimal Personalized PageRank computationResearch Paper

Personalized PageRank assigns importance to vertices relative to a chosen seed. A walk starts at the seed and stops with probability α\alphaα at each step; its stopping location has the PageRank distribution. Small teleportation probabilities let the walk explore farther, but make the running time of the classic local computation grow. This matters when…

47 thms3 active usersReviewed
🏆Completed
Computational GeometryOptimization·Captain: mikedeng1

Tight Coreset Bounds for (k,z)(k,z)(k,z)-Clustering in Euclidean and Doubling MetricsResearch Paper

A coreset compresses a clustering dataset into a weighted subset whose cost approximates the original cost for every permitted choice of centers. An optimization algorithm can work on that subset after the input has been read. The number of retained locations therefore matters independently of the time needed to inspect the original data. The question here…

17 thms3 active usersReviewed
🏆Completed
Algebraic GeometryComplexity Theory·Captain: iris

Multivariate Resultants: Complexity and Applications to Real FeasibilityResearch Paper

Valiant's hypothesis VP≠VNP\mathrm{VP}\neq\mathrm{VNP}VP=VNP is the algebraic analogue of P≠NP\mathrm{P}\neq\mathrm{NP}P=NP: it asserts that the permanent, and with it every polynomial family defined by exponential sums of easy polynomials, has no polynomial-size arithmetic circuits (Valiant 1979; Bürgisser 2000). Hardness results under this hypothesis tell which natural…

59 thms3 active usersReviewed
🏆Completed
CombinatoricscryptographyInformation Theory·Captain: mikedeng1

Expanding Codes with Polynomial StretchResearch Paper

A collection of sparse parity equations can involve almost as many variables as its total number of variable occurrences. This expansion property excludes small linear dependencies and is relevant to the complexity of recognizing noisy planted equations. It is therefore useful to distinguish what expansion guarantees from what it leaves possible. Hair and…

23 thms3 active usersReviewed
PreviousPage 3 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