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.

1360 open missions

Missions

626–650 of 1360
Open1360Completed139All1499
OptimizationProbability·Captain: mikedeng1

Adaptivity Gaps for Welfare-Maximizing Pooled TestingResearch Paper

Pooled screening uses a limited number of assays to clear potentially valuable individuals or resources. A negative test certifies every member of its pool as healthy. With a fixed budget, later tests can respond to earlier outcomes, directing the remaining resources toward different people after positive and negative results. The mathematical question is…

17 thms2 active usersReviewed
Computational GeometryGraph Theory·Captain: mikedeng1

A Sublinear Approximation Algorithm for Minimum Dilation Trees in the PlaneResearch Paper

A geometric spanning tree connects a finite set of points using straight segments between pairs of points. A route between two vertices follows the tree edges. Its length can exceed the direct Euclidean distance substantially, even when the tree has minimum total edge length. The minimum dilation tree problem asks for a tree that controls the worst such…

14 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Settling the Query Complexity of Weighted Stochastic MatchingResearch Paper

A matching pairs vertices using edges that share no endpoint. When the edges describe uncertain compatibility, finding a good pairing requires tests: an edge can be used only after learning that it is present. In the non-adaptive query model, all tests must be selected before their outcomes are observed. The motivating kidney-exchange interpretation makes…

36 thms2 active usersReviewed
Computational ComplexityProbabilityQuantum Information+1·Captain: mikedeng1

Quantum Query Lower Bounds from Classical Moment MatchingResearch Paper

Many properties studied in property testing and distribution estimation are symmetric: they depend on a function f:[N]→[N]f:[N]\to[N]f:[N]→[N] only through how often each output value occurs. Examples are the number of distinct values (support size), element distinctness, collision-freeness, and kkk-distinctness. A standard way to prove classical query lower bounds for such…

20 thms2 active usersReviewed
CombinatoricsQuantum Information·Captain: mikedeng1

Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space StabilityResearch Paper

Locality asks how far information must travel in a network before each node can choose its part of a global solution. The basic model is the LOCAL model (Linial 1992; Peleg 2000): nodes communicate in synchronous rounds, and the round complexity of a problem is the number of rounds needed. Colouring a cycle is the standard test case. For every fixed q≥3q\ge3q≥3, qqq…

24 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

UPPcc is Not Closed Under IntersectionResearch Paper

In the unbounded-error model of communication complexity, Alice holds a∈Aa\in Aa∈A, Bob holds b∈Bb\in Bb∈B, each has an unlimited supply of private random bits, and they must output a known function F(a,b)∈{−1,1}F(a,b)\in\{-1,1\}F(a,b)∈{−1,1} with probability strictly greater than 1/21/21/2 on every input. The cost U(F)U(F)U(F) is the least number of bits they must exchange. The class UPPcc\mathrm{UPP}^{cc}UPPcc collec…

35 thms2 active usersReviewed
Graph TheoryMarkov ChainProbability·Captain: mikedeng1

Sampling Matchings in Near-linear TimeResearch Paper

A matching is a collection of edges in a graph such that no vertex belongs to two selected edges. Random matchings are basic examples in sampling and approximate counting: when every matching has equal weight, the normalizing constant counts all matchings. More generally, edge weights specify a distribution that favors some matchings over others. The…

30 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

XOR Games at Full Tilt: The Hardness of Binary Nonlocal GamesResearch Paper

A nonlocal game tests correlations between two separated players. A referee samples a pair of questions, sends one question to each player, and checks their answers. The players can agree on a strategy beforehand but cannot communicate after receiving the questions. Researchers in quantum information and computational complexity study how shared…

25 thms2 active usersReviewed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

The Complexity of Private Signaling in Nonatomic Routing GamesResearch Paper

A traffic principal can know more about road conditions than individual drivers. Sending every driver the same report is one option; sending different private route recommendations is another. The computational question is whether a principal can find private recommendations with low expected total latency while keeping each recommendation approximately…

19 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

New Lower Bounds for Private PAC LearningResearch Paper

A learner trained on sensitive examples must control what its output reveals about any one record. Differential privacy imposes that control by comparing output probabilities when a single record changes. The resulting sample requirement can exceed the requirement for ordinary classification. A useful lower bound should explain which independent learning…

35 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Semi-Streaming Reachability and Shortest Paths in n1/3+o(1)n^{1/3+o(1)}n1/3+o(1) PassesResearch Paper

In the graph streaming model the edges of an input graph arrive one at a time in an arbitrary order, and an algorithm may make several passes over this stream. In the semi-streaming setting it may use O~(n)=O(n polylog n)\tilde O(n)=O(n\,\mathrm{polylog}\,n)O~(n)=O(npolylogn) bits of memory on an nnn-vertex graph, and the goal is to use as few passes as possible. Single-source reachability in…

20 thms2 active usersReviewed
cryptographyProbabilityQuantum Information+1·Captain: iris

Towards the Impossibility of Imperfectly Complete Key Agreement in the QROMResearch Paper

Two parties who share no secret want to agree on a key over a public channel, using only a shared random function HHH that everyone, the eavesdropper included, can query. Merkle's puzzle protocol achieves a quadratic gap: the honest parties make nnn queries and an eavesdropper needs about n2n^2n2. For classical parties this gap is optimal. Impagliazzo and Rudich…

33 thms2 active usersReviewed
Bandit AlgorithmsComplexity TheoryQuantum Information·Captain: iris

Gap-Agnostic Ground-State Preparation via Quantum BanditsResearch Paper

Preparing the ground state (the lowest-energy eigenvector) of a Hamiltonian HHH is a basic task in quantum simulation, quantum chemistry and condensed-matter physics. In full generality it is hard: deciding the ground energy of local Hamiltonians to inverse-polynomial precision is QMA-complete (Kitaev–Shen–Vyalyi 2002). Efficient algorithms therefore assume…

52 thms2 active usersReviewed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: iris

Toward an Optimal Quantum Algorithm for Geometrically Local Hamiltonian SimulationResearch Paper

Simulating the time evolution e−iHTe^{-iHT}e−iHT of a many-body Hamiltonian is the task quantum computers were first proposed for, and lattice Hamiltonians with short-range interactions are its most common instance in condensed-matter physics and quantum chemistry. On hardware with nearest-neighbor connectivity, the relevant cost is the circuit depth: how many layers…

28 thms2 active usersReviewed
cryptographyInformation TheoryQuantum Information·Captain: iris

Flexible rigidity: Compiling generic trusted-preparation protocols into sequential device-independent protocolsResearch Paper

Many quantum cryptographic protocols are prepare-and-measure protocols: Alice prepares quantum states drawn from a known ensemble and sends them to a possibly dishonest Bob. Uncloneable encryption, copy protection and blind randomness expansion are examples. Their security proofs assume that Alice's preparation device is trusted, which is a device-dependent…

98 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Sublinear Sample Size Suffices for Learning Mixtures of Gaussians up to IsometryResearch Paper

Learning a mixture of Gaussians from samples is a central problem of statistics and learning theory. For mixtures of kkk spherical Gaussians in Rd\mathbb R^dRd, proper density estimation in total variation needs Θ~(kd/ε2)\tilde\Theta(kd/\varepsilon^2)Θ~(kd/ε2) samples (Ashtiani, Ben-David, Harvey, Liaw, Mehrabian, Plan, J. ACM 2020), and the linear dependence on ddd cannot be…

21 thms2 active usersReviewed
Complexity TheoryGraph TheoryMathematical Logic+1·Captain: iris

First-Order Model Checking on Monadically Dependent Graph ClassesResearch Paper

First-order model checking asks, for a finite graph GGG and a first-order sentence φ\varphiφ over the adjacency relation, whether G⊨φG\models\varphiG⊨φ. Problems such as kkk-Dominating-Set, kkk-Clique and HHH-Subgraph-Isomorphism are instances. On general graphs the problem is believed not to be fixed-parameter tractable (fpt) in ∣φ∣|\varphi|∣φ∣, since this is equivalent to …

38 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability+1·Captain: Shuze Chen

Iterative Randomized Rounding for kkk-Median in General and Euclidean MetricsResearch Paper

In metric k-median one is given clients and candidate facilities in a metric space and a budget kkk, and must open at most kkk facilities so that the total distance from clients to their nearest open facility is as small as possible. It is a basic clustering objective and a long-standing test case for approximation techniques: LP rounding, primal–dual methods,…

14 thms2 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: iris

Quantum Fair ExchangeResearch Paper

In a fair exchange, two parties each hold an item and want to swap them so that either both receive the other's item or neither loses anything. With classical data, a trusted third party can escrow copies of both items. Chung, Lee, Raizes and Thyagarajan (Quantum Fair Exchange, STOC 2027 submission, manuscript of 2026-11-02) ask the same question when the…

24 thms2 active usersReviewed
AlgebracryptographyTheoretical Computer Science·Captain: iris

Counterexamples to Beyond-Johnson Proximity Gaps over Binary FieldsResearch Paper

Hash-based succinct proof systems (SNARKs) check that committed words are close to a Reed–Solomon code by querying a few entries of a random combination f+zgf+zgf+zg of two words. Their soundness rests on proximity gaps: if f+zgf+zgf+zg agrees with a codeword on many positions, then fff and ggg agree with codewords on many common positions, except for a small set of challenges …

28 thms2 active usersReviewed
Machine LearningQuantum InformationStatistics+1·Captain: iris

Agnostic Product Mixed State Tomography via Robust StatisticsResearch Paper

Quantum state tomography asks for a classical description of an unknown state ρ\rhoρ from measurements on copies of it. Learning a general nnn-qubit state needs exponentially many copies, so one asks instead for the best approximation within a simple class. The agnostic version makes no assumption on ρ\rhoρ: the learner must compete with opt\mathrm{opt}opt, the…

32 thms2 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Distributional Quantum Query ComplexityResearch Paper

Query complexity measures how many input bits an algorithm must read. Many lower bounds in complexity theory, from communication complexity to cryptographic hardness, are proved by composition: the outer function fff is evaluated on the outputs of nnn copies of an inner function ggg, and the cost of f∘gf\circ gf∘g is bounded below by a product of the two costs. For…

37 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: Shuze Chen

Optimal Multi-Item Auctions with I.I.D. ValuesResearch Paper

A seller with several items and several buyers who wants the largest expected revenue faces the multi-item version of Myerson's problem. For one item, Myerson (1981) gives the answer in closed form for every prior. For several items, explicit optimal mechanisms are known only in special cases: two items under analytic conditions, a few uniform or…

16 thms2 active usersReviewed
Complexity TheorycryptographyLogic+1·Captain: Shuze Chen

SNARGs from any Witness Encryption, and MoreResearch Paper

A witness encryption (WE) scheme for an NP relation RRR lets anyone encrypt a bit bbb under an instance xxx; whoever knows a witness www with R(x,w)=1R(x,w)=1R(x,w)=1 can decrypt, and for xxx outside the language the ciphertext hides bbb (Garg–Gentry–Sahai–Waters 2013). Jain, Kalai, Lombardi and Mathialagan (JKLM 2025) showed that WE yields SNARGs for NP, provided the scheme comes…

11 thms2 active usersReviewed
Graph TheoryLinear OptimizationOptimization+1·Captain: Shuze Chen

Approaching Optimality for Dense Bipartite MatchingsResearch Paper

The maximum bipartite matching problem asks, for a bipartite graph GGG with sides LLL and RRR, for the largest number ν(G)\nu(G)ν(G) of edges no two of which share a vertex. It is the most basic case of maximum flow and of linear programming over an integral polytope, and its running time on dense graphs has long been a test of algorithmic technique. Combinatorial…

17 thms2 active usersReviewed
PreviousPage 26 of 55Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn690113
3SHshivm1630
4PAparclytaxel150172
5MTmartelus trismortuus1050
6GAgaryholm900
7WCwcysai8486
8A1a142857a7518
9SCSenrui Chen6757
10BEbersubs6574

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