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.

1496 missions

Missions

676–700 of 1496
Open1374Completed122All1496
Computational ComplexityMathematical Logic·Captain: mikedeng1

Approximate Counting and the Provability of Combinatorial PrinciplesResearch Paper

Randomized algorithm analysis repeatedly estimates the fraction of inputs accepted by a Boolean computation. A formal theory of approximate counting specifies which assertions about those estimates can be used in a proof. Its strength matters when comparing probabilistic reasoning with combinatorial principles. Korten, Li, Oliveira and Ren study this…

17 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Sublinear-Time Algorithms on Massive Data StreamsResearch Paper

Graph property testing asks how much of a graph must be inspected to distinguish a property from a substantial violation. A query may be expensive even when storing previous answers is cheap. This motivates streaming testing: vertices pass once through an interface, and an algorithm chooses which arriving vertices to inspect. The question is whether answers…

31 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Accepting Subcubes and the Approximability of Complete Boolean Min-CSPsResearch Paper

In a minimum constraint satisfaction problem (Min-CSP) the input is a set of Boolean variables and a list of constraints, and the goal is an assignment violating as few constraints as possible. On general instances, Min-2-CNF Deletion has an O(log⁡n)O(\sqrt{\log n})O(logn​)-approximation, while a constant factor would refute the Unique Games Conjecture; for Min-3-SAT any…

40 thms2 active usersReviewed
CombinatoricsConvex OptimizationProbability+1·Captain: Shuze Chen

Subexponential Approximation of the Permanent in Deterministic Polynomial TimeResearch Paper

The permanent of an n×nn\times nn×n matrix AAA is

23 thms2 active usersReviewed
Algebraic GeometryComplexity TheoryComputational Complexity·Captain: iris

Some algebraic and geometric computations in CH via Chow formsResearch Paper

Decomposing an algebraic variety into equidimensional components is a basic task of computer algebra: most algorithms for irreducible decomposition first split a variety by dimension and then factor each piece. Andrews, Garg, Oliveira and Schost (arXiv:2611.05289) place several problems about equidimensional components in the counting hierarchy CH, where…

38 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and SpannersResearch Paper

A directed network can have very different distances in its two directions. A compact family of trees is useful when paths must be represented using edges of the original network, while limiting the number of structures that store each vertex. Distance oracles, spanners and routing schemes use such representations. The structural result considered here…

16 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Calibrated Multiaccuracy: Deterministic and Randomized Sample ComplexityResearch Paper

Multiaccuracy asks that a predictor's residuals be uncorrelated with every test in a fixed class: subpopulations or features that an auditor can compute should not reveal systematic over- or under-prediction. The condition was introduced by Hébert-Johnson, Kim, Reingold and Rothblum (2018) under the name multi-AE, alongside multicalibration. Calibration asks…

25 thms2 active usersReviewed
Functional AnalysisQuantum InformationRandom Matrix Theory+1·Captain: mikedeng1

Quantum Advantage for Distributed Symmetry BreakingResearch Paper

In distributed computing, symmetry breaking asks the nodes of a network, all running the same program, to produce locally different outputs; the basic example is a proper colouring of a cycle. In the classical LOCAL model, 3-colouring an nnn-cycle requires Θ(log⁡∗n)\Theta(\log^* n)Θ(log∗n) communication rounds, with or without randomness (Linial 1992). Whether quantum…

30 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Beyond IP= PSPACE and QIP= PSPACE: Interactive Proofs in Arbitrary Physical TheoriesResearch Paper

An interactive proof lets a verifier with bounded computational power check a claim by exchanging messages with an all-powerful prover. Two theorems describe the power of the model: classical interactive proofs decide exactly polynomial space, IP=PSPACE\mathsf{IP}=\mathsf{PSPACE}IP=PSPACE (Lund, Fortnow, Karloff and Nisan; Shamir; Shen, 1990–92), and quantum interactive…

26 thms2 active usersReviewed
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
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
PreviousPage 28 of 60Next

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