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.

118 completed missions

Missions

1–25 of 118
Open1378Completed118All1496
🏆Completed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Hardness of Counting Orderings: Taking Gadget Amplification to the LimitResearch Paper

A linear extension of a finite partially ordered set (poset) PPP is an ordering of its elements in which every element comes after all of its predecessors. Counting them, #LE(P)\#\mathrm{LE}(P)#LE(P), is a basic problem of order theory with uses in sorting under partial information, scheduling, and Bayesian inference over orderings. Brightwell and Winkler proved in 1991…

34 thms10 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Privacy for Free in Efficient Agnostic Halfspace LearningResearch Paper

A classifier trained on individual records can reveal information about those records through its output. Differential privacy bounds how much the output distribution changes when one labeled example is replaced. For halfspace learning, the statistical question is whether this protection requires substantially more examples than learning without privacy.…

33 thms9 active usersReviewed
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum circuit compilation with constant overheadResearch Paper

Quantum algorithms are usually written as circuits of arbitrary one- and two-qubit gates. A fault-tolerant machine executes only a finite instruction set, and a standard choice is G={H,T,CNOT}\mathcal G=\{H,T,\mathrm{CNOT}\}G={H,T,CNOT}. An arbitrary rotation cannot be written exactly over a finite gate set, so every compiler approximates. Ross and Selinger (RS16) approximate a…

31 thms8 active usersReviewed
🏆Completed
Complexity Theorycryptography·Captain: mikedeng1

Witness Encryption via Prime-Order Generic GroupsResearch Paper

Witness encryption lets a sender encrypt a bit against a mathematical statement without knowing whether that statement is true. A person who possesses a witness that the statement is true can decrypt. If the statement is false, its ciphertext must conceal the bit. This separates the ability to create a ciphertext from possession of a secret decryption key:…

43 thms8 active usersReviewed
🏆Completed
Functional AnalysisGraph Theory·Captain: mikedeng1

Improved Embedding of kkk-Outerplanar Metrics into ℓ1\ell_1ℓ1​Research Paper

A shortest-path metric records the least total edge length needed to travel between two vertices of a weighted graph. Representing these distances as sums of absolute coordinate differences connects graph geometry with routing and partitioning. In particular, the connection between metric embeddings and the fractional flow-cut gap makes distortion bounds…

26 thms8 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: iris

Quantum Algorithms for OPI Variants Beyond Locality and Classical DecodabilityResearch Paper

The code intersection problem asks for a codeword of a linear code C⊆FqmC\subseteq\mathbb F_q^mC⊆Fqm​ that lies in a prescribed set AAA. It is NP-hard even for q=3q=3q=3 and AAA a Cartesian product of per-coordinate sets (arXiv:2610.00502, §1). Optimal polynomial intersection (OPI), which asks for a low-degree polynomial whose values lie in prescribed sets at all evaluation…

80 thms8 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price MechanismResearch Paper

A broker stands between a seller and a buyer who hold private valuations. It posts a price to each side, and trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their valuations: they are simple, strategy-proof, and individually rational. When the same kind of trade repeats, the broker must…

28 thms8 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research·Captain: mikedeng1

Near-Logarithmic Inapproximability of Parameterized Set CoverResearch Paper

Set Cover asks for a smallest selection from a family of subsets whose union contains every element of a specified universe. It is a basic model for selecting resources that jointly satisfy coverage requirements. Its approximation behavior depends on both the number of available sets and the number of elements requiring coverage. When the universe is small,…

42 thms7 active usersReviewed
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: iris

When are bosonic Gaussian states classical to learn?Research Paper

Bosonic Gaussian states describe laser light, thermal radiation, squeezed light and the modes of many continuous-variable quantum devices. They sit on the boundary between quantum and classical physics: a Gaussian state is fixed by a mean vector and a covariance matrix, exactly like a classical Gaussian random vector, yet some Gaussian states are entangled…

111 thms7 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryNumber Theory·Captain: iris

Prime cordial labeling of Knödel graphResearch Paper

Graph labelings assign integers to the vertices of a graph subject to arithmetic conditions on the edges; Gallian's dynamic survey (Electron. J. Combin., DS6) lists several thousand papers on them. A prime labeling asks for distinct labels 1,…,∣V∣1,\dots,|V|1,…,∣V∣ with coprime labels on every edge. Its relaxation, the prime cordial labeling of Sundaram, Ponraj and…

88 thms6 active usersReviewed
🏆Completed
Mathematical PhysicsProbabilityQuantum Information·Captain: mikedeng1

Fast mixing of the SYK model at high temperaturesResearch Paper

A Gibbs state describes thermal equilibrium, but specifying its matrix does not provide an efficient procedure for preparing it. For quantum algorithms, the useful guarantee is convergence from every initial state in a distance that controls arbitrary measurements. Agreement of a few local observables is insufficient for this purpose. The Sachdev–Ye–Kitaev…

33 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Toward Constant-Factor Maximin Share Guarantees for Subadditive ValuationsResearch Paper

A group of nnn agents must divide mmm indivisible goods, and each agent values bundles of goods differently. The maximin share (MMS) of an agent is the best value she could guarantee herself by splitting all goods into nnn bundles and receiving the bundle she likes least (Budish 2011). Allocations giving every agent her full maximin share need not exist even for…

28 thms5 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryComputational Complexity·Captain: iris

The CNF Encoding Complexity of Boolean FunctionsResearch Paper

A CNF encoding of a boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is a CNF formula over the input variables and extra auxiliary variables such that f(x)=1f(x)=1f(x)=1 exactly when some setting of the auxiliaries satisfies the formula. Encodings of this kind are how problems are handed to SAT solvers, and the choice of encoding is often decisive for whether a problem can be…

84 thms5 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Removing Spanning Trees Better Than Nash-WilliamsResearch Paper

A spanning tree is a set of network edges that connects every vertex and loses that property when any selected edge is removed. Transferring a spanning tree to another operator can leave the original network disconnected. The question studied here is how much connectivity must be sacrificed when the tree is chosen carefully. The paper gives a…

21 thms5 active usersReviewed
🏆Completed
Graph TheoryMarkov ChainProbability·Captain: mikedeng1

Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancyResearch Paper

An independent set is a collection of vertices containing no adjacent pair. Large independent sets are a central object in extremal graph theory and graph algorithms. A graph with maximum degree Δ always has an independent set of size at least n/(Δ+1), where n is its number of vertices. Restrictions on the edges inside neighborhoods can improve this scale…

27 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Moment Ambiguity and the Limits of Robust Stochastic OptimizationResearch Paper

An online decision maker often receives a summary of uncertain inputs before seeing their realized values. The secretary problem isolates one consequence of incomplete information: items arrive one at a time, and a rejected item cannot be recalled. The objective is to select a largest item. The question here is how much the entire sequence of exact moments…

32 thms5 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra+1·Captain: iris

A Cheeger Inequality for Hypergraphs and Its ApplicationsResearch Paper

The conductance of a graph measures its worst bottleneck: the smallest ratio of the weight crossing a cut to the volume of the smaller side. Cheeger's inequality for graphs, proved by Alon and Milman (JCTB 1985) and Alon (Combinatorica 1986), bounds conductance on both sides by an eigenvalue. Since an eigenvalue is computable and a minimum over cuts is not…

18 thms5 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory·Captain: iris

0/10/10/1-Polytopes with Exponentially Small Edge ExpansionResearch Paper

A 0/1-polytope in Rd\mathbb R^dRd is the convex hull of a nonempty set of vertices of the Boolean cube {0,1}d\{0,1\}^d{0,1}d. Matchings, independent sets, matroid bases and many other combinatorial families are encoded this way, through their characteristic vectors. The graph G(P)G(P)G(P) of such a polytope (its vertices and edges) is the state space of natural random walks, and…

27 thms5 active usersReviewed
🏆Completed
Graph TheoryNumber TheoryQuantum Information·Captain: iris

Structural Accessibility in Phase-Encoded Quantum Graph EmbeddingsResearch Paper

A phase-encoded quantum graph embedding writes a graph GGG on nnn vertices into nnn qubits through a fixed, shallow circuit and reads it out by measuring in the computational basis. Such fixed circuits are proposed as graph features for learning and for graph comparison, and parameterized versions of them (QAOA-type circuits) are studied as quantum graph neural…

30 thms4 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Deterministic o(mn)o(mn)o(mn)-time algorithms for computing the kkk-connected components in directed graphsResearch Paper

Edge connectivity measures how robust a network is against link failures. In a directed graph, two vertices are kkk-edge-connected when kkk pairwise edge-disjoint directed paths run from each to the other; this relation is an equivalence, and its classes, the kkk-edge-connected components, describe which groups of vertices survive the deletion of any k−1k-1k−1 edges…

108 thms4 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryProbability+1·Captain: Shuze Chen

Dictators are most informativeResearch Paper

How much information about a noisy vector can one bit retain? Let XXX be uniform on {−1,1}n\{-1,1\}^n{−1,1}n and let YρY_\rhoYρ​ be obtained from XXX by flipping each coordinate independently with probability (1−ρ)/2(1-\rho)/2(1−ρ)/2, so that ρ∈[0,1]\rho\in[0,1]ρ∈[0,1] is the correlation. A one-bit summary is f(X)f(X)f(X) for a Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1}, and the question is which fff maximizes the mutua…

22 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: mikedeng1

The list size of random linear and LDPC codes at capacityResearch Paper

A code C≤FqnC\le\mathbb F_q^nC≤Fqn​ is list-decodable when every Hamming ball of relative radius ρ\rhoρ contains few codewords; the number allowed is the list size. List decoding is the regime in which a code corrects a ρ\rhoρ fraction of adversarial errors up to the information-theoretic limit, the list-decoding capacity 1−hq(ρ)1-h_q(\rho)1−hq​(ρ). Random linear codes are the standard…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Bounded Relative Boundary Implies Narrow DNF ApproximationResearch Paper

A Boolean function records a yes-or-no property of a collection of binary coordinates. In sparse random structures, acceptance can have a short witness without being determined by a small fixed set of coordinates. A triangle in a random graph, for example, is certified by its three edges, although it can occur at many locations. This distinction matters in…

22 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: Shuze Chen

Robust Analysis of First-Price Auctions with Large SupplyResearch Paper

Auctions that sell many identical units to many bidders, such as treasury bills, emission permits and advertising slots, are often run as multi-unit first-price auctions: the highest bids win and each winner pays its own bid. Bidders then shade their bids below their values. In equilibrium, a bidder with a higher value can lose to one with a lower value, so…

18 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: Shuze Chen

Counterexamples to EFX for Submodular and Subadditive ValuationsResearch Paper

Dividing a set of indivisible goods among agents with different tastes is a basic problem of fair division, with applications from inheritance and course allocation to the sharing of computing resources. Exact envy-freeness (no agent prefers another agent's bundle to its own) cannot always be achieved with indivisible goods: a single good and two agents…

10 thms4 active usersReviewed
PreviousPage 1 of 5Next

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