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

751–775 of 1499
Open1321Completed178All1499
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

The Power and Limits of Money Burning in Bilateral TradeResearch Paper

In bilateral trade a seller owns one indivisible good and a buyer may want it. Each trader privately knows their own value. A mechanism asks both for reports and decides whether to trade and what each trader pays or receives. A mechanism is strongly budget-balanced (SBB) when the buyer's payment always equals the seller's receipt. It is weakly…

38 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

A Near-Optimal Parallel Algorithm for Finding Matroid BasesResearch Paper

A matroid M=(E,I)M=(E,\mathcal I)M=(E,I) on a finite ground set EEE of nnn elements is a family I\mathcal II of independent sets that contains ∅\emptyset∅, is closed under taking subsets, and satisfies the exchange property. Spanning forests of graphs and bases of vector configurations are the standard examples. A basis is a maximal independent set. Because the number of…

27 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Finding and Certifying Weighted Minimum Cuts with Cut QueriesResearch Paper

A cut query asks for the total capacity joining a specified set of vertices to its complement. It provides an aggregate measurement of an unknown graph rather than a list of its edges. Researchers studying graph query complexity ask how many such measurements suffice to determine an optimization value. For minimum cut, a related question concerns…

23 thms2 active usersReviewed
Algorithmic Game TheoryAnalysis·Captain: mikedeng1

Tight Bounds on the Menu-Size Complexity of Approximately Optimal Auctions with Two ItemsResearch Paper

A seller offering two items to one buyer can offer lotteries as well as deterministic purchases. Describing a lottery requires two allocation probabilities and a price, and an auction may offer many such alternatives. Menu size measures how many distinct nonnull alternatives are required. The resulting question concerns the complexity of implementing a…

21 thms2 active usersReviewed
Computational ComplexityGraph TheoryQuantum Information·Captain: mikedeng1

A Quantum Lower Bound for Triangle FindingResearch Paper

A triangle is a set of three distinct vertices joined by all three possible edges. In the adjacency-matrix query model, a graph is hidden and an algorithm learns whether two vertices are adjacent by querying their pair. Triangle finding asks the algorithm to return a triangle whenever one exists. The resource being measured is the number of queries;…

20 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
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
PreviousPage 31 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