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

501–525 of 1499
Open1321Completed178All1499
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian CertificatesResearch Paper

A proper coloring assigns a label to each vertex of a graph so that adjacent vertices have different labels. A graph is three-colorable when such an assignment exists using three labels. Knowing that three colors suffice does not supply the assignment. The approximation question asks how many colors an efficient algorithm can guarantee under that promise.…

22 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed GraphsResearch Paper

The restricted shortest paths problem asks for a route that is short while respecting a separate cost budget. Travel time and monetary cost need not favor the same route. The same distinction appears in quality-of-service routing, where delay is optimized subject to another resource constraint. Ashvinkumar discusses these applications and the difficulty of…

16 thms3 active usersReviewed
Algorithmic Game TheoryComputational ComplexityLinear Optimization·Captain: mikedeng1

Designing Information in a Forest: Algorithmic AspectsResearch Paper

An informed sender can influence several decision makers by choosing what to reveal about a common unknown state. When some decision makers observe messages addressed to others, an information policy must account for those observations. A policy designed for independent private messages may have a different effect once the messages become visible elsewhere.…

14 thms3 active usersReviewed
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
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Is Randomness Necessary for Adaptive Data Analysis?Research Paper

A dataset is often reused to answer questions chosen after seeing earlier answers. Each answer can influence the next question, so the usual guarantee for one question fixed in advance does not automatically extend to the resulting interaction. Adaptive data analysis asks what a mechanism can reliably reveal about a population from a single finite sample in…

14 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
CombinatoricsComputational ComplexityGraph Theory·Captain: mikedeng1

Triangle-Freeness: Estimation Is as Easy as TestingResearch Paper

An algorithm examining a large graph may have time to inspect only a small part of its adjacency matrix. Property testing asks whether the graph has a specified property or requires a substantial number of edge changes to acquire it. Distance estimation asks how many changes are needed, to a prescribed additive accuracy. For triangle-freeness, a tester can…

17 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
ProbabilityQuantum Information·Captain: mikedeng1

Near-Optimal Mixedness Testing with Pauli MeasurementsResearch Paper

An experimenter may need to determine whether a prepared quantum system is maximally mixed without reconstructing its entire state. The restriction on available measurements matters: measuring each qubit separately gives a different information budget from a measurement that jointly processes many qubits or many copies. Mixedness testing asks for a decision…

19 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
Graph Theory·Captain: mikedeng1

Quantitative Results on Super-Ramanujan GraphsResearch Paper

A ddd-regular graph always has ddd as its largest adjacency eigenvalue. How far the remaining eigenvalues stay from ddd measures how well the graph expands, and good spectral expanders are used throughout pseudorandomness, error-correcting codes, derandomization and the design of communication networks. The Alon–Boppana bound shows that for a fixed degree ddd the…

20 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
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Cutting a Cake For Human Consumption: An Elementary nnn-agent Cake Cutting ProtocolResearch Paper

Envy-free cake cutting asks how to divide a divisible resource among nnn agents with different preferences so that no agent prefers another agent's share to her own. It is one of the founding problems of fair division, and its query complexity is a standard benchmark for the theory of fair-division protocols.

65 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
🏆Completed
CombinatoricsDiscrete GeometryRandom Matrix Theory·Captain: mikedeng1

The Sharp Dimension Bound in the Johnson–Lindenstrauss LemmaResearch Paper

A collection of vectors is often used through the distances between its elements. Reducing the number of coordinates is useful only if those distances remain reliable. Euclidean dimension reduction asks how small the target dimension can be when every pairwise distance must be preserved to a specified relative accuracy. The question is relevant to metric…

5 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
Complexity TheoryQuantum Information·Captain: iris

Quantum State Search with Classical Interactive AdviceResearch Paper

Unstructured search over 2n2^n2n items needs Θ(2n/2)\Theta(2^{n/2})Θ(2n/2) quantum queries (Grover; Bennett, Bernstein, Brassard and Vazirani), and a prover who knows the marked item removes that cost by sending its nnn-bit address. The question behind this mission is whether classical communication helps in the same way when the hidden object is a quantum state.

39 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
PreviousPage 21 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