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

376–400 of 1499
Open1321Completed178All1499
CombinatoricsGraph TheoryTheoretical Computer Science+1·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Testable Sanitization via Boundary GeometryResearch Paper

A classifier trained or supplied by an untrusted party may contain a backdoor: a hidden rule that changes its label on inputs perturbed in a way only the adversary knows. Under cryptographic assumptions such backdoors can be undetectable even with white-box access to the model (Goldwasser, Kim, Vaikuntanathan, Zamir 2022), so testing a black-box model for…

17 thms3 active usersReviewed
CombinatoricsComplexity TheoryInformation Theory+2·Captain: Shuze Chen

Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper

Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nnn nodes, or a forest, is written as a word of 2n2n2n brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…

18 thms3 active usersReviewed
Markov ChainProbabilityRandom Matrix Theory+2·Captain: Shuze Chen

High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear RegressionResearch Paper

The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: a Gibbs measure on {±1}d\{\pm1\}^d{±1}d whose interactions are a random Gaussian matrix. Sampling from it is a benchmark problem for Markov chain Monte Carlo. At high temperature (inverse temperature β\betaβ below an absolute constant) Glauber dynamics is known to mix rapidly, while at low temperature…

16 thms3 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory·Captain: Shuze Chen

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable DecompositionResearch Paper

Minimum Bisection asks whether the vertex set of a graph can be split into two halves, up to one vertex, with at most kkk edges between them. It is the unweighted two-part case of the graph-partitioning problem of Kernighan and Lin (1970) and is NP-complete (Garey, Johnson and Stockmeyer, 1976). Parameterized by the cut size kkk, it became a test case for the…

29 thms3 active usersReviewed
CombinatoricsComplexity TheoryGroup Theory+2·Captain: Shuze Chen

Group Isomorphism: Depth-2122\frac{1}{2}221​ Circuits and Lower BoundsResearch Paper

Group Isomorphism (GpI) asks whether two finite groups, each given by its full multiplication table (its Cayley table), are isomorphic. With n=∣G∣n=|G|n=∣G∣, Miller's generator-enumeration algorithm decides it in time nlog⁡2n+O(1)n^{\log_2 n+O(1)}nlog2​n+O(1), because every group of order nnn is generated by at most log⁡2n\log_2 nlog2​n elements. Whether GpI is in polynomial time is open, and so is the…

17 thms3 active usersReviewed
AlgebracryptographyInformation Theory+1·Captain: Shuze Chen

Reed–Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic ProofsResearch Paper

Reed–Solomon codes are the codes behind most deployed proof systems that use the FRI protocol and its successors (STARK provers such as ProveKit, ZisK and LambdaVM). The soundness of those protocols reduces to two combinatorial facts about the code: how many codewords can lie close to a received word (list decoding), and whether closeness of a random linear…

25 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
Computational ComplexityInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Optimal XOR Lemmas for Information ComplexityResearch Paper

Information complexity measures how much two parties must reveal to each other about their inputs in order to compute a function together. It lower-bounds randomized communication complexity, equals the amortized communication cost of many independent copies (Braverman–Rao 2014; Braverman 2015), and underlies lower bounds for set disjointness, data streams…

23 thms3 active usersReviewed
Mathematical PhysicsNumerical AnalysisOptimization+2·Captain: Shuze Chen

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick ModelResearch Paper

The Sherrington–Kirkpatrick (SK) model is the basic mean-field spin glass: for a random symmetric Gaussian matrix AAA, find a spin vector σ∈{−1,1}N\sigma\in\{-1,1\}^Nσ∈{−1,1}N maximizing the energy HN(σ)=12σ⊤AσH_N(\sigma)=\tfrac12\sigma^\top A\sigmaHN​(σ)=21​σ⊤Aσ. Finding the exact maximizer is a hard combinatorial problem in the worst case, and the question of how close polynomial-time algorithms can…

23 thms3 active usersReviewed
AnalysisMachine LearningProbability+1·Captain: Shuze Chen

Error accumulation in reverse diffusion with an imperfect score: beyond path-space analysesResearch Paper

Diffusion models generate samples from a data distribution ppp on Rd\mathbb R^dRd by running a stochastic differential equation backwards in time. The drift of the backward equation involves the score ∇log⁡pt\nabla\log p_t∇logpt​ of the noised data distribution, which is not known and is replaced by a neural-network estimate s^\hat ss^ trained by a squared loss. The standard…

18 thms3 active usersReviewed
Group TheoryQuantum InformationRepresentation Theory·Captain: mikedeng1

(Almost) quadruply optimal unitary designs in 1DResearch Paper

Random unitary operations are used in quantum benchmarking, learning and information processing. A generic Haar-random operation on n qubits requires an exponential number of elementary gates. A unitary design replaces that full distribution by an implementable ensemble whose low-order moments reproduce Haar randomness to a specified accuracy. The resource…

43 thms3 active usersReviewed
Graph TheoryOptimizationTheoretical Computer Science·Captain: mikedeng1

Rounded Potentials Certify Exact Maximum FlowResearch Paper

A maximum flow measures how much material can move from a source to a sink while respecting directed edge capacities and conserving material at other vertices. The classical certificate for its exact value contains both a feasible flow and a separating cut of the same value. The maximum-flow/minimum-cut theorem guarantees that these witnesses exist Ford and…

23 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label SymmetryResearch Paper

A collision in a function is a pair of distinct inputs with the same output. Collision search is a basic test of the resources needed to attack an idealized hash function. Query counts alone leave out the memory used to retain previously observed values. The distinction matters for the quantum algorithms considered here: storing a table of values and…

27 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
Complexity TheorycryptographyNumber Theory·Captain: mikedeng1

SVP Is NP-Hard for Some Rank-2 Cyclotomic ModulesResearch Paper

Researchers in lattice complexity study how algebraic restrictions affect the difficulty of finding short vectors. A module lattice carries scalar multiplication by a ring of algebraic integers, in addition to ordinary integer addition. Fixing its module rank at two still leaves an unbounded lattice dimension as the number field varies. The question here…

25 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

3SUM Made Simpler (Without Matrix Multiplication), kkk-SUM Hypothesis Refuted for Odd kkk, and Real 3SUM/APSP DerandomizedResearch Paper

The 3SUM problem asks whether numbers from given collections satisfy an additive relation. Its running time matters in fine-grained complexity, where reductions compare the computational costs of different problems. A batch version asks which of many query numbers belong to a sumset. It retains information that a single yes-or-no decision discards, and…

12 thms3 active usersReviewed
Computational ComplexityGraph TheoryLinear Optimization+1·Captain: mikedeng1

An LP Algorithm for Counting Eulerian Orientations Through the Lens of Promise PolymorphismsResearch Paper

A finite graph can be oriented so that each vertex has equally many incoming and outgoing edges precisely when every vertex has even degree. Counting the orientations subject to local restrictions is a different computational problem. A vertex can favor some local arrangements, forbid others, or attach complex weights to them. The resulting weighted sum…

40 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation SymmetryResearch Paper

A query algorithm learns an unknown input by asking for individual entries. Its cost counts those requests, allowing arbitrary computation between them. Quantum algorithms can query a superposition of positions, so comparing their query cost with randomized classical algorithms isolates an information advantage from implementation costs. For promise…

23 thms3 active usersReviewed
Markov ChainMathematical PhysicsQuantum Information·Captain: mikedeng1

Efficient classical simulation of Fermi-Hubbard models with Kramers symmetryResearch Paper

The partition function is the normalization that assigns thermal weights to a quantum system's energy levels. Computing it gives access to equilibrium quantities such as free energy. For interacting electrons, the underlying state space grows exponentially with the number of modes, making exact matrix calculations impractical even when the input Hamiltonian…

17 thms3 active usersReviewed
Information TheoryProbability·Captain: mikedeng1

The Necessity of Elias Codes in the Global Clock ModelResearch Paper

A multiple-access channel is a resource on which a transmission succeeds precisely when one player transmits in a time slot. If several transmit, they interfere; if none transmit, the slot is unused. Distributed systems use randomized transmission rules because their participants may arrive at different times and may not know how many other participants…

24 thms3 active usersReviewed
Computational ComplexityGraph Theory·Captain: mikedeng1

Vertex Deletion on HHH-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation SchemesResearch Paper

Vertex deletion asks how many vertices must be removed to make a graph satisfy a prescribed condition. Removing vertices to eliminate every edge gives Vertex Cover; removing them to eliminate every cycle gives Feedback Vertex Set. These problems arise within a common formulation: the remaining graph must have bounded treewidth and satisfy a fixed logical…

30 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
Information TheoryTheoretical Computer Science·Captain: Shuze Chen

Random Access to LZ-End: Faster and DeterministicResearch Paper

Lempel–Ziv compression replaces every repeated fragment of a string by a pointer to an earlier occurrence; it underlies gzip, ZIP and PNG. A compressed text is only useful if it can be queried without decompressing it, and the most basic query is random access: given a position iii, return the character S[i]S[i]S[i]. For grammar-compressed strings this is settled up…

24 thms3 active usersReviewed
PreviousPage 16 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