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.

178 completed missions

Missions

1–25 of 178
Open1321Completed178All1499
🏆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
Complexity TheorycryptographyQuantum Information+1·Captain: Shuze Chen

Information Loss Is All You Need: TC^0 Pseudorandomness from Worst-Case LatticesResearch Paper

Learning with errors (LWE) is the standard source of post-quantum hardness: given many noisy inner products As+e mod qA s + e \bmod qAs+emodq of a secret sss, distinguish them from uniform. Regev showed in 2005 that this is as hard, for quantum algorithms, as worst-case approximate lattice problems (Reg05). Removing the random error makes the samples deterministic: learning…

138 thms9 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear SeparatorsResearch Paper

An independent set in a graph is a collection of vertices with no edge between any two selected vertices. With a rational value attached to each vertex, maximum weight independent set asks for the largest possible sum of selected values. This expresses selection problems in which edges represent pairwise incompatibility. The distinction between a graph and…

92 thms9 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
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Distributionally Robust Search: The Power of Information and the Limits of MomentsResearch Paper

Searching an ordered list for a target drawn from a probability distribution is one of the oldest problems in algorithms: when the distribution ppp is known, an optimal or near-optimal comparison strategy (an optimal binary search tree, or median search Mehlhorn 1975) costs O(OPT(p))O(\mathrm{OPT}(p))O(OPT(p)) queries in expectation, which can be far below the …

62 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
Complexity TheoryQuantum Information·Captain: mikedeng1

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph modelResearch Paper

A property tester inspects a small part of an input and decides whether the input has a specified property or is far from every input having that property. For a large graph, the number of inspected adjacency entries can matter more than the time needed for computations between inspections. A quantum query permits a coherent superposition of such…

47 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Best-of-Many-Worlds MMS Allocation for Chores with Sublinear DisposalsResearch Paper

Dividing undesirable tasks gives a cost to every recipient. A person asked to divide all tasks into equal shares may still be unable to find a share she considers acceptable once other people's preferences must also be respected. This tension matters in fair division: a benchmark based only on each person's own costs need not be simultaneously achievable by…

28 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchReinforcement Learning·Captain: iris

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive PoliciesResearch Paper

Adaptive policies — recommendation systems, dynamic pricing rules, treatment protocols, trading strategies — choose actions based on the state they observe. A natural audit question is how much of a policy's performance comes from that adaptivity, as opposed to the average mix of actions it plays. Answering it requires a benchmark that plays the same…

20 thms5 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
Formal VerificationMathematical LogicTheoretical Computer Science+1·Captain: Shuze Chen

Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper

Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…

31 thms5 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: mikedeng1

Random-Oracle Unitary Synthesis is ImpossibleResearch Paper

Unitary synthesis asks how a quantum circuit can implement a prescribed transformation when it may consult a classical function in quantum superposition. The choice of function can carry substantial information about the requested transformation. The question changes when that function must be sampled uniformly: how many queries are needed before the…

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

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous MessagesResearch Paper

Secure distributed computation asks parties to disclose enough information to evaluate a function while limiting what the evaluator can learn about their individual inputs. In the private simultaneous messages model, the parties share randomness hidden from the evaluator, each sends one message, and the evaluator recovers the answer. Even when each party…

30 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
PreviousPage 1 of 8Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin140143
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8BOBoomShaKaLaaaKa93100
9GAgaryholm900
10WCwcysai8486

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