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.

1499 missions

Missions

851–875 of 1499
Open1321Completed178All1499
Graph TheoryOperations ResearchOptimization+1·Captain: iris

Improved Approximations for Two-Edge-Connected and Two-Vertex-Connected Spanning SubgraphsResearch Paper

A network that has to survive the failure of any single link must be 2-edge-connected: it stays connected after the deletion of any one edge. The minimum 2-edge-connected spanning subgraph problem (2ECSS) asks for such a network with the fewest links inside a given graph. It is a basic survivable network design problem, NP-hard (a solution on nnn vertices has…

46 thms2 active usersReviewed
Convex OptimizationFunctional AnalysisProbability+1·Captain: iris

Thin-shell stability and heat-adjoint hypercontractivity: logconcave sampling with sesteric complexity from a cold startResearch Paper

Sampling from a logconcave distribution π∝e−V\pi\propto e^{-V}π∝e−V on Rn\mathbb R^nRn, given only an oracle that evaluates the convex function VVV, is the basic subroutine of volume computation, integration, rounding and private optimization. The cost is measured in queries to the oracle. Most samplers need a warm start, an initial distribution already close to π\piπ, and…

31 thms2 active usersReviewed
CombinatoricsGroup TheoryProbability·Captain: Shuze Chen

Sharp Second-Order Thresholds for Random Algebraic CoverageResearch Paper

From kkk elements of an abelian group one obtains 2k2^k2k indexed subset sums; in a noncommutative group the analogous objects are products taken in the original input order. A basic all-target question is when these representations reach every element of the group. Erdős and Rényi studied this model for arbitrary finite groups, including noncommutative ones, and…

22 thms2 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory+2·Captain: Shuze Chen

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper

A graph homomorphism partition function assigns to a symmetric weight matrix M∈Rn×nM\in\mathbb R^{n\times n}M∈Rn×n and a graph G=(V,E)G=(V,E)G=(V,E) the number

23 thms2 active usersReviewed
🏆Completed
AlgebraComplexity TheoryLinear algebra+1·Captain: Shuze Chen

New lower bounds on tensor rank of (n,2,m)(n,2,m)(n,2,m) matrix multiplication with GPT-6 AstraResearch Paper

Every fast matrix multiplication algorithm starts from an identity that computes a fixed-shape product with few multiplications. Strassen's 1969 algorithm (Str69) multiplies two 2×22\times 22×2 matrices with 7 instead of 8 multiplications, and applying such an identity recursively turns RRR multiplications for a k×lk\times lk×l by l×ml\times ml×m product into an …

12 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: iris

Geometrically Constrained Learning I: Agnostically Learning Adversarially Robust ClassifiersResearch Paper

A classifier is adversarially robust when a small change to its input rarely changes its output. Backdoors planted in learned models ([GKVZ22], FOCS 2022) and the post-processing defences built against them ([GSVV25], STOC 2025) assume that a well-behaved classifier can be trained in the first place. Under Gaussian data this question has a clean form.…

28 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

The Power of Interaction in Locally Edge-Private Subgraph CountingResearch Paper

Subgraph counts (the number of triangles, stars, cycles or cliques in a network) are among the most widely used summaries of a graph. When the edges are sensitive relationships, releasing such counts leaks information, and differential privacy (Dwork, McSherry, Nissim, Smith 2006) is the standard way to bound that leakage. In the local model no trusted…

27 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: Shuze Chen

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic WeightsResearch Paper

Counting complexity asks which weighted sums over exponentially many assignments can be evaluated exactly in polynomial time. The Holant framework expresses such sums by placing a local function on every vertex of a graph and a Boolean variable on every edge. One then multiplies the local values and sums over all edge assignments (Valiant 2008; Cai–Lu–Xia…

22 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: iris

Likelihood-Ratio Learning under Weak Overlap via Analytic Temporal EliminationResearch Paper

Many statistical procedures need the log density ratio ℓ⋆=log⁡(p/q)\ell^\star=\log(p/q)ℓ⋆=log(p/q) between two laws PPP and QQQ that are known only through samples: covariate-shift correction, off-policy evaluation, simulation-based inference and mutual-information estimation all reweight one sample by eℓ⋆e^{\ell^\star}eℓ⋆. The standard direct method is balanced logistic density-ratio…

19 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research+2·Captain: Shuze Chen

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid ProphetResearch Paper

In the classical secretary problem (Dynkin 1963; Lindley 1961) nnn distinct values arrive in uniformly random order and the decision maker must accept or reject each one immediately and irrevocably. The aim is to select the largest. Rejecting about the first n/en/en/e values and then taking the first value larger than all earlier ones succeeds with probability…

11 thms2 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

Constant-Factor Approximation for Capacitated Clustering in Low Dimensions with (1+ε)k(1+\varepsilon)k(1+ε)k CentersResearch Paper

Capacitated clustering models facilities that can serve only a bounded number of customers: servers with a limit on concurrent jobs, depots that can supply a bounded number of stores, districts of roughly equal population. Without capacities, kkk-median and kkk-means admit polynomial-time approximation schemes in fixed-dimensional Euclidean space and in metrics…

22 thms2 active usersReviewed
Complexity TheorycryptographyProbability+1·Captain: Shuze Chen

Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced AssumptionsResearch Paper

Randomized algorithms and cryptographic protocols assume uniform random bits, while physical sources of randomness are biased and correlated. A seedless extractor is one deterministic function that turns every source in a class into nearly uniform bits, provided the source has enough min-entropy H∞(X)=−log⁡2max⁡xPr⁡[X=x]H_\infty(X)=-\log_2\max_x\Pr[X=x]H∞​(X)=−log2​maxx​Pr[X=x]. For general sources this is…

20 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Subgaussian Vector Balancing by an Ising ModelResearch Paper

Vector balancing asks how to choose signs for short vectors so that their sum remains controlled in every direction. A distribution over signs offers a probabilistic version: every linear measurement of the resulting signed sum should have a small exponential moment. This is useful when a randomized assignment must balance several numerical covariates…

17 thms2 active usersReviewed
CombinatoricsComputational ComplexityLinear algebra·Captain: mikedeng1

Kadison–Singer in Deterministic Polynomial TimeResearch Paper

Matrix discrepancy asks how to assign plus and minus signs to a collection of matrices so their signed sum is small. A bound independent of the matrix dimension is useful when the matrices represent many simultaneous quadratic measurements: cancellation must hold in every direction, rather than for a single scalar sum. The Kadison–Singer problem, in its…

20 thms2 active usersReviewed
Numerical AnalysisProbability·Captain: mikedeng1

Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random MatricesResearch Paper

Gaussian elimination with partial pivoting (GEPP) solves a dense real linear system by exchanging rows and subtracting multiples of a pivot row. Its numerical accuracy depends partly on whether these operations create entries much larger than the input entries. This matters to numerical analysts studying when a fast general-purpose solver can lose accuracy,…

33 thms2 active usersReviewed
cryptography·Captain: mikedeng1

Merkle Trees Minimize Verifier Complexity in the ROMResearch Paper

A vector commitment lets a holder summarize a binary vector by a commitment and later justify a claimed bit at a chosen position. The verifier receives the commitment, position, bit and witness rather than the whole vector. This interface is used in authenticated data structures and as a component of larger cryptographic protocols. When many openings must…

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

Language Generation Beyond Adversarial ExamplesResearch Paper

Researchers in learning theory study whether examples of an unknown language suffice to generate new valid strings. The task asks for a new member of the target language after each received example, with errors allowed during an initial finite period. Language generation in the limit, introduced by Kleinberg and Mullainathan, supplies a mathematical model…

28 thms2 active usersReviewed
Computational Complexity·Captain: mikedeng1

Better Upper Bounds for Square-Root-Sum and Straight-Line Program PositivityResearch Paper

A short arithmetic computation can describe an integer too long to write out efficiently. Repeated squaring already produces this effect using only the literal 1, addition and multiplication. Determining the sign of the resulting integer is therefore a separate computational question from evaluating it in binary. This question matters in exact numerical…

9 thms2 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisProbability·Captain: mikedeng1

A dimension-free bound for the isoperimetric constant of unconditional log-concave measuresResearch Paper

A probability distribution in high dimension can be difficult to control even when every one-dimensional coordinate has variance one. A Poincaré inequality controls the variance of every locally Lipschitz real function by its average squared gradient. For log-concave distributions, this functional inequality also controls isoperimetry. It therefore connects…

24 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A Tight Ω~(m)\widetilde\Omega (\sqrt m)Ω(m​) Information-theoretic Lower Bound for Randomized Online Set CoverResearch Paper

Online set cover asks how many sets must be purchased when the elements requiring coverage arrive one at a time. It is relevant to the analysis of algorithms that make irrevocable covering decisions before learning which demands will occur. Knowing the available sets does not reveal the future demands. The mathematical question is how much this missing…

17 thms2 active usersReviewed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Binary Two-Way Codes with Optimal Erasure ResilienceResearch Paper

A sender often receives replies while transmitting a message. If those replies can also be lost, a reliability guarantee must account for losses in both directions. Coding theory asks how much adversarial loss a communication scheme can tolerate while still conveying every message exactly. This mission concerns binary two-way codes: deterministic protocols…

10 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Even Coarse Matching Estimates Require Nearly Linear Streaming SpaceResearch Paper

A streaming algorithm reads graph updates in sequence while retaining a limited memory state. For matching, there is a practical distinction between storing an actual set of disjoint edges and reporting only how many edges an optimal such set contains. A large matching itself takes substantial space to write down, whereas its size is a single number. This…

17 thms2 active usersReviewed
Complexity TheoryOptimization·Captain: mikedeng1

The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded CoefficientsResearch Paper

A quadratic program minimizes a polynomial of degree at most two over a specified feasible set. Even the unit cube permits nonconvex objectives, so an exact global minimum can be computationally difficult to find. A Karush–Kuhn–Tucker point, or KKT point, instead satisfies the first-order conditions appropriate to the coordinate constraints. Researchers…

17 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Tight Release Schedules under Distribution ShiftResearch Paper

A deployed predictor can remain unchanged while its owner collects labels, retains observations and computes candidate replacements. A limit on replacing the deployed predictor therefore creates a statistical scheduling question: how much prediction error is unavoidable when only a few replacements are allowed? This differs from restricting access to labels…

14 thms2 active usersReviewed
Complexity TheoryInformation TheoryQuantum Information·Captain: mikedeng1

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching ProblemResearch Paper

One-way communication complexity asks how much information Alice must send when Bob has a different input and must decide a joint property. It provides a setting in which classical and quantum information can be compared without imposing restrictions on local computation. The Boolean Hidden Matching problem is an established example: a short quantum message…

20 thms2 active usersReviewed
PreviousPage 35 of 60Next

Top contributors

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

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