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

451–475 of 1496
Open1374Completed122All1496
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree GraphsResearch Paper

A multi-spin system assigns one of finitely many spins to each vertex of a graph. Each assignment receives a weight determined by local vertex preferences and interactions across edges. The sum of these weights, the partition function, is useful both as a counting quantity and as the normalizing constant of a probability distribution. Computing this sum…

25 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal Tolerant Testing of Lindbladian DissipationResearch Paper

A quantum device can change because of coherent Hamiltonian motion or because of coupling to its environment. Distinguishing these contributions matters when assessing whether physical noise lies below a prescribed tolerance. Reconstructing every interaction would answer a substantially larger question than such a test requires. Bao, Cai and Shang study the…

21 thms3 active usersReviewed
Computational ComplexityGraph TheoryInformation Theory·Captain: mikedeng1

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent SetResearch Paper

A graph stream presents the edges of a graph one at a time while an algorithm keeps a limited working memory. Maximum Clique asks for a largest set of vertices with every pair joined by an edge. Streaming algorithms for this problem are relevant to the study of what graph information can be retained in a small memory: the desired output is a set of…

22 thms3 active usersReviewed
CombinatoricsQuantum InformationRepresentation Theory·Captain: mikedeng1

Optimal cloning of mixed statesResearch Paper

The no-cloning theorem rules out a device that reproduces every unknown quantum state exactly. Experiments and algorithms instead operate with nonzero error, so a quantitative question remains: how many identical input copies are needed to produce additional copies while keeping the entire output close to the desired product state? The distinction between…

26 thms3 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

Ruling out Fast Approximation Algorithms for Clique, Biclique, Collinearity, and Arithmetic ProgressionsResearch Paper

A clique is a collection of vertices in a graph with an edge between every pair. Detecting a fixed small clique is a basic graph algorithm problem. A natural approximation question asks whether a promise of a much larger clique helps detect a smaller one. In particular, could a program distinguish a graph containing a large fixed clique from a graph…

25 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
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

Arc Kayles is PSPACE-completeResearch Paper

Arc Kayles is a two-player game on a finite undirected graph. The players alternate, and a move picks an edge uvuvuv of the current graph and deletes both endpoints. Under normal play the first player without a legal move loses. The winner is the player who plays the last edge of a maximal matching of the original graph, so Arc Kayles is to maximal matchings…

19 thms3 active usersReviewed
Quantum InformationQuantum Mechanics·Captain: mikedeng1

Sharp universal death of entanglement threshold for Pauli HamiltoniansResearch Paper

A quantum system in thermal equilibrium can retain correlations that cannot be reproduced by mixing independently prepared single-qubit states. For researchers studying quantum many-body systems and classical descriptions of quantum states, a basic question is when sufficiently high temperature rules out this entanglement uniformly over an interaction…

18 thms3 active usersReviewed
Computational ComplexityProbabilityQuantum Information·Captain: mikedeng1

BQP⊆IP Does Not RelativizeResearch Paper

A quantum computation can produce an answer that a classical computer cannot efficiently reproduce. An interactive proof asks whether a classical verifier can nevertheless check that answer by exchanging messages with an unrestricted prover. The verifier must accept correct claims with high probability and reject incorrect claims regardless of the prover’s…

25 thms3 active usersReviewed
Graph TheoryOptimizationProbability·Captain: mikedeng1

Optimal Sample Complexity for Max-CutResearch Paper

A maximum cut partitions a graph's vertices into two parts to maximize the total weight of edges between them. When a graph is too large to inspect in full, estimating this optimum from a small sample can reduce the amount of graph data needed. A value coreset is a small reweighted graph whose maximum-cut value approximates the original value. Returning a…

34 thms3 active usersReviewed
cryptographyNumber Theory·Captain: mikedeng1

A New Approach to Reducing Modulus Requirements in Homomorphic Computation: Precision Allocation in CKKSResearch Paper

CKKS is a homomorphic encryption scheme for approximate arithmetic on real and complex numbers. A single ciphertext carries several independent values, called slots, with a common scale controlling the size of numerical errors relative to messages. This representation makes unequal accuracy requirements relevant: a computation may need many accurate bits in…

11 thms3 active usersReviewed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Improved Impossibility Bounds for Maximin Share AllocationsResearch Paper

Dividing indivisible goods among agents with additive valuations is a central problem of fair division, and the maximin share (MMS) is its most studied fairness benchmark: an agent's MMS is the value she can guarantee herself by partitioning all goods into nnn bundles and receiving the worst one. Kurokawa, Procaccia and Wang showed that an allocation giving…

21 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depthResearch Paper

Random circuit sampling asks for samples from the bitstring distribution produced by a given quantum circuit acting on the all-zero input. Analyses of this task and its experimental benchmarks use statistical predictions about random circuits. A central prediction concerns how the probability of one fixed output varies when the circuit is sampled…

18 thms3 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Last-Iterate Stationarity of Muon with Finitely Many Newton-Schulz IterationsResearch Paper

Muon is an optimizer for matrix-shaped parameters in neural-network training. At each step it forms a momentum average of stochastic gradients and replaces that matrix by an approximately orthogonalized version before taking a step. In practice the orthogonalization is not the exact polar factor. It is a fixed small number JJJ (commonly J=5J=5J=5) of quintic Newton–…

18 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Forgetting Alternation and BlossomsResearch Paper

A maximum cardinality matching of a general graph can be found by repeatedly augmenting the current matching along a maximal set of vertex-disjoint shortest augmenting paths. Hopcroft and Karp showed that O(n)O(\sqrt n)O(n​) such phases suffice, so the whole difficulty is to compute one maximal set of disjoint shortest augmenting paths in nearly linear time. In…

29 thms3 active usersReviewed
Algorithmic Game TheoryComplexity TheoryTheoretical Computer Science·Captain: iris

The Complexity of Correlated Equilibria Beyond Normal-Form GamesResearch Paper

A correlated equilibrium (CE) is a distribution over strategy profiles from which no player gains by applying any swap deviation, a map that replaces each recommended strategy by another one. In normal-form games (finitely many pure strategies) CE are the solutions of a linear program, and in games of polynomial type exact CE can be computed in polynomial…

48 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
Algorithmic Game TheoryCombinatoricsOptimization·Captain: iris

Approximation and Hardness in Optimization GamesResearch Paper

Deciding the winner of a two-player alternating-turn game with perfect information is typically PSPACE-hard, which raises the question of which natural games admit tractable strategies. A classical exception is the Shannon switching game and its matroid generalization: Lehman (1964) characterized the winner and gave polynomial-time winning strategies, and…

48 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Strong Selective and List-Decoding Direct Product Theorems for Quantum Query ComplexityResearch Paper

A direct product theorem says that solving kkk independent instances of a problem is kkk times as hard as solving one, and that an algorithm with fewer resources fails on the kkk-fold problem with probability exponentially close to 111 in kkk. The second, "strong" form is what lower-bound applications need. Time-space tradeoffs in the style of Borodin and Cook cut a…

48 thms3 active usersReviewed
Information TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Structural Lower Bounds with Persistent Quantum MemoryResearch Paper

How many copies of an unknown quantum state does a learner need to estimate many expectation values Tr⁡(ρGj)\operatorname{Tr}(\rho G_j)Tr(ρGj​) at once? The answer depends sharply on the learner's quantum memory. A learner that measures each copy and keeps only classical records can need exponentially more copies than one that stores many copies and measures them jointly (C…

27 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Online Metric Problems via Randomly Perturbed Work FunctionsResearch Paper

In metric allocation a unit of mass is spread over the nnn points of a metric space and must be redistributed online as convex cost functions arrive at the points, paying for transport and for service. The problem was introduced by Bansal and Coester [BC22] (ESA 2022) as a common generalization of fractional kkk-server and of metrical task systems (MTS), and it…

25 thms3 active usersReviewed
CombinatoricsInformation TheoryQuantum Information+1·Captain: iris

Binary code rate bounds via classical-quantum channelsResearch Paper

A binary error-correcting code of length nnn is a set C⊆{0,1}n\mathcal C\subseteq\{0,1\}^nC⊆{0,1}n of codewords. Its minimum distance dmin⁡(C)d_{\min}(\mathcal C)dmin​(C), the least Hamming distance between two distinct codewords, guarantees correction of every pattern of fewer than dmin⁡/2d_{\min}/2dmin​/2 bit flips, wherever they occur. How many codewords such a guarantee allows is measured by the asymp…

25 thms3 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: iris

Almost Every 3-Uniform Hypergraph is Class 1Research Paper

Colouring the edges of a graph or hypergraph so that intersecting edges get different colours is the same as partitioning its edges into matchings. The problem appears in scheduling, communication networks and design theory. For ordinary graphs the answer is almost settled: by Vizing's theorem every graph GGG has χ′(G)∈{Δ(G),Δ(G)+1}\chi'(G) \in \{\Delta(G), \Delta(G)+1\}χ′(G)∈{Δ(G),Δ(G)+1}, and…

43 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

The Conditional Geometry of Statistical VerificationResearch Paper

A learner that hands over a classifier can be asked to justify it. In statistical verification an untrusted prover proposes a hypothesis and a verifier, using its own private labeled samples, either accepts a hypothesis whose risk is within ε\varepsilonε of the best in the class or rejects. The question is how many private samples verification needs compared…

46 thms3 active usersReviewed
Complexity TheoryInformation TheoryProbability·Captain: iris

Can Many Instances Be Cheaper Than One? The Price of Agreement in EliminationResearch Paper

Direct-sum and direct-product questions ask how the cost of solving kkk independent instances of a communication problem relates to the cost of one. Elimination asks for much less than computing: given kkk instances, the parties only have to output some answer vector σ∈{0,1}k\sigma\in\{0,1\}^kσ∈{0,1}k that is not the true one. Guessing a uniformly random σ\sigmaσ already errs…

36 thms3 active usersReviewed
PreviousPage 19 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