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.

1496 missions

Missions

876–900 of 1496
Open1374Completed122All1496
Complexity Theory·Captain: mikedeng1

Multi-Access Randomness Saves Space, Even for Halting AlgorithmsResearch Paper

Space complexity asks how much writable memory a computation needs. Randomness introduces another resource: a machine can consult a tape of independent fair bits without paying for those bits as work space. Whether it may return to an earlier random bit, and whether it must halt on every possible tape, affect the resulting model. These distinctions matter…

21 thms2 active usersReviewed
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 thms2 active usersReviewed
Quantum InformationStatistics·Captain: mikedeng1

Optimal Purity Estimation with Incoherent MeasurementsResearch Paper

The purity of a quantum state measures how far its statistical description is from a pure state. For a subsystem of a larger pure system, its negative logarithm is the second Rényi entropy, which measures entanglement with the rest of the system. Experimental protocols based on randomized measurements use purity to characterize quantum states without…

31 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: mikedeng1

Exact Agreement Expansion up to the Top via Non-polarityResearch Paper

An agreement test checks whether a collection of local functions comes from one global function. Each set KKK of a weighted family carries a local function FK:K→ΣF_K:K\to\SigmaFK​:K→Σ. The test samples a smaller set HHH, then two sets K,K′⊇HK,K'\supseteq HK,K′⊇H, and accepts when FKF_KFK​ and FK′F_{K'}FK′​ agree on HHH. Soundness says that a test that rarely rejects forces most FKF_KFK​ to be…

12 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

k-Coloring is Faster than Computing the Chromatic NumberResearch Paper

Graph coloring is one of the basic NP-complete problems, and its exact exponential-time complexity has been studied for decades. Computing the chromatic number χ(G)\chi(G)χ(G) of an nnn-vertex graph takes O∗(2n)O^*(2^n)O∗(2n) time by the inclusion–exclusion algorithm of Björklund, Husfeldt and Koivisto (SIAM J. Comput. 2009), where O∗O^*O∗ hides factors polynomial in the input size.…

17 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: mikedeng1

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation FactorsResearch Paper

The weighted girth of an undirected graph is the minimum total edge weight of a cycle. Computing this quantity asks for the least expensive closed route with no repeated intermediate vertex or edge. Approximation algorithms trade precision for running time: instead of finding the minimum exactly, they return a number within a specified multiplicative…

7 thms2 active usersReviewed
Convex OptimizationProbabilityStatistics+1·Captain: mikedeng1

An Exact-Radius Convex Characterization of Discrete Identity TestingResearch Paper

Identity testing asks whether observations follow a specified probability distribution or a distribution farther than a prescribed distance from it. For a known finite reference, the amount of data needed can depend on the distribution of mass across labels, including a dominant atom, a light tail, and labels with zero reference probability. A bound that…

24 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximation and Even Arity Hardness for Boolean Constraint SatisfactionResearch Paper

Boolean Max-kkk-CSP asks for an assignment of {−1,1}\{-1,1\}{−1,1} values to variables that maximizes the total weight of satisfied constraints, where each constraint is an arbitrary Boolean predicate on at most kkk variables. Because the predicates may differ from constraint to constraint, the best approximation ratio for this problem measures the loss caused by the arity…

23 thms2 active usersReviewed
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…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra·Captain: mikedeng1

Uniform adjacency-degree probes from differential rigidityResearch Paper

A tree can be described without vertex names by asking which matrix quantities survive relabelling. Its adjacency matrix records which vertices are joined, while its degree matrix places each vertex's number of neighbours on the diagonal. The trace of any polynomial in these two matrices is unchanged by relabelling. The question is how much information one…

10 thms2 active usersReviewed
Discrete GeometryFunctional Analysis·Captain: mikedeng1

Bourgain's Theorem for a Union of Euclidean Metric SpacesResearch Paper

A distance-preserving representation of a metric space by vectors allows geometric methods to be applied to distances that were not originally given by coordinates. In applications of metric embeddings, the relevant cost is the largest multiplicative change in pairwise distances. Bourgain's theorem bounds that cost in terms of the number of points. The…

39 thms2 active usersReviewed
Complexity TheoryLinear algebra·Captain: mikedeng1

Explicit tensors beyond the linear flattening barrierResearch Paper

A three-dimensional array describes a bilinear computation: fixing two input vectors and contracting against two coordinates produces an output vector. A decomposition of the array into simple products gives a way to perform this computation with a specified number of products of linear forms. Tensor rank measures the shortest such decomposition. Border rank…

20 thms2 active usersReviewed
CombinatoricsComputational Complexity·Captain: mikedeng1

Breaking the 2n2^n2n barrier for graph kkk-coloringResearch Paper

A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. Exact algorithms for deciding whether a graph admits a specified number of colors are studied in computational complexity because their running times measure how much of an exponential search can be avoided. The relevant parameter here is the number of vertices,…

12 thms2 active usersReviewed
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 thms2 active usersReviewed
Machine LearningProbabilityTheory of Computation·Captain: mikedeng1

The Price of List Replicability: Tight Bounds for Bias EstimationResearch Paper

A statistical estimate can be accurate while changing from one independent sample to another. List replicability asks for more: for each underlying distribution there must be a small fixed list of accurate answers, and the algorithm must return one of them with high probability. The list depends on the distribution, rather than the observed samples or…

27 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisTheoretical Computer Science·Captain: mikedeng1

A Linear Lower Bound for Convex Body Chasing in Every NormResearch Paper

Convex body chasing is a basic online problem in metric geometry and online algorithms: an algorithm must stay inside a sequence of convex constraints revealed one at a time while moving as little as possible. It was introduced by Friedman and Linial (FL93, Discrete Comput. Geom. 1993) and is the geometric core of online convex optimization with switching…

16 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

Lower Bounds for Parallel Diffusion SamplingResearch Paper

A diffusion sampler produces a random vector by repeatedly asking for information about a distribution after Gaussian noise has been added. Such queries are often the expensive part of generation. Parallel implementations can evaluate many proposed locations simultaneously, but the next batch can still depend on earlier answers. The question is how many…

25 thms2 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Facility Location with Customer IncompatibilitiesResearch Paper

Facility location asks which facilities to open and how to assign clients to them so that opening costs plus connection costs are as small as possible. It underlies distribution-system design and customer allocation, and its variants (uncapacitated facility location, kkk-median, capacitated facility location) are standard testbeds for approximation…

20 thms2 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

An EPTAS for Max-Cut on Interval GraphsResearch Paper

In Max-Cut one is given a graph G=(V,E)G=(V,E)G=(V,E) and asks for a set S⊆VS\subseteq VS⊆V maximizing cutG(S)\mathrm{cut}_G(S)cutG​(S), the number of edges with exactly one endpoint in SSS; mc(G)\mathrm{mc}(G)mc(G) denotes the maximum. On general graphs the Goemans–Williamson algorithm achieves the ratio αGW≈0.878\alpha_{GW}\approx0.878αGW​≈0.878, and beating it is NP-hard under the Unique Games Conjecture; …

31 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MAResearch Paper

A proof system combines a claim, a witness, and a verifier that decides whether to accept the witness. Classical randomized verification allows the verifier to toss private coins while receiving an ordinary bit string. Quantum verification can also receive a quantum state and perform coherent operations. Determining which of these resources increases…

32 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

The Strong Secretary Conjecture is True for Linear MatroidsResearch Paper

In the Matroid Secretary Problem, introduced by Babaioff, Immorlica and Kleinberg (SODA 2007; J. ACM version), the elements of a matroid carry nonnegative weights and arrive in uniformly random order. On each arrival the algorithm learns the element's weight and must decide irrevocably whether to keep it, while the kept set stays independent. The model…

18 thms2 active usersReviewed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided DiscrepancyResearch Paper

Dividing indivisible goods fairly is a basic problem of computational social choice (survey: Amanatidis et al., 2023). In group fair division the agents are organized into kkk groups, every group receives one common bundle, and the members of a group may value the goods very differently, as with families sharing an inheritance or departments sharing…

23 thms2 active usersReviewed
cryptography·Captain: mikedeng1

Affine Advantage in Guess-type Attacks on Goldreich’s PRGs: Characterization and CountermeasuresResearch Paper

A local pseudorandom generator computes each output bit from a small public selection of seed bits. This permits parallel evaluation, but also gives seed-recovery attacks many small equations involving the same hidden seed. The predicate applied to each selection therefore matters alongside the seed length and number of outputs. The source studies…

22 thms2 active usersReviewed
Complexity TheoryLinear algebra·Captain: mikedeng1

Worst-Case to Average-Case Reductions for Basic Linear AlgebraResearch Paper

Matrix multiplication, inversion, solving linear systems, rank and the determinant have closely related worst-case running times: fast multiplication gives fast algorithms for the others through classical reductions. Average-case behaviour is a different matter, because the standard reductions pass through highly structured matrices, on which an algorithm…

19 thms2 active usersReviewed
Quantum InformationQuantum Mechanics·Captain: mikedeng1

Spectral gap of Lee-Yang HamiltoniansResearch Paper

The spectral gap of a quantum Hamiltonian is the energy difference between its two lowest eigenvalues, counting multiplicity. A lower bound on this difference is useful when assessing the cost of preparing a ground state by adiabatic evolution. For an interacting system, such a bound often depends on the interaction graph or coupling strengths. Rayudu and…

21 thms2 active usersReviewed
PreviousPage 36 of 60Next

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