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

976–1000 of 1499
Open1321Completed178All1499
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Three Standard Deviations Suffice While One Does NotResearch Paper

A collection of measurements can depend on the same binary decisions. Each decision contributes a real coefficient to each measurement, and choosing its sign changes all measurements at once. Discrepancy theory asks how small all resulting totals can be made simultaneously. In the matrix formulation, the columns describe decisions, the rows describe…

15 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Witness Isolation with Inverse-Polylogarithmic Success Implies NP in P/polyResearch Paper

A witness is a binary string certifying that an instance has a positive answer. For a Boolean circuit, a witness is an assignment on which the circuit outputs one. Many reductions in complexity theory become useful when exactly one witness survives. Witness isolation therefore asks for a procedure that restricts a satisfiable instance while retaining…

21 thms2 active usersReviewed
Complexity TheoryHarmonic AnalysisLinear algebra·Captain: mikedeng1

Lower Bounds for Memory-Efficient Differentially Private Continual CountingResearch Paper

Differentially private training of machine-learning models repeatedly releases noisy prefix sums of gradients. The mechanism with the best known accuracy for this task is the matrix mechanism: factor the prefix-sum matrix AnA_nAn​ as An=BCA_n=BCAn​=BC, and release B(Cx+z)=Anx+BzB(Cx+z)=A_nx+BzB(Cx+z)=An​x+Bz for Gaussian noise zzz. Fichtenberger, Henzinger and Upadhyay gave a lower-triangular Toeplitz sq…

37 thms2 active usersReviewed
Complexity TheoryProbability·Captain: mikedeng1

Random (log⁡n\log{n}logn)-CNF Formulas Are Hard for Depth-222 Frege with Modular GatesResearch Paper

A propositional contradiction can have very different proof lengths in different systems. Polynomial calculus measures the algebraic complexity of a contradiction by the largest polynomial degree needed to derive the constant one from its equations. For random formulas, the relevant question is whether many constraints make a contradiction easy to certify…

26 thms2 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: mikedeng1

On the optimality of truncation among binary linear sketchesResearch Paper

A binary linear sketch compresses a binary vector by reporting parity measurements: each output bit is the sum modulo two of selected input coordinates. Such sketches support distributed computation because parity measurements of a sum can be obtained by adding the separate measurements. When two terminals observe correlated data, however, preserving this…

14 thms2 active usersReviewed
🏆Completed
AlgebraAnalysis·Captain: mikedeng1

Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational FunctionsResearch Paper

A real sequence is holonomic when it satisfies a linear recurrence whose coefficients are rational functions of the index. Such sequences include many combinatorial sums and the coefficient sequences of solutions of linear differential equations with polynomial coefficients. Whether a holonomic sequence is positive, or ultimately positive, is relevant to…

16 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Tight Bounds for Tusnády's Problem in the PlaneResearch Paper

A coloring assigns each point one of two signs, interpreted as membership in two groups. For a region of the plane, its imbalance is the absolute difference between the numbers of points of the two signs inside it. Small imbalance simultaneously over many regions is a basic objective of geometric discrepancy theory. Axis-parallel rectangles are a natural…

13 thms2 active usersReviewed
🏆Completed
CombinatoricsComplexity Theory·Captain: mikedeng1

Monotone circuit lower bounds from spread matchingsResearch Paper

A monotone Boolean circuit computes with AND and OR gates only. Exponential lower bounds for such circuits are a long line of unconditional results in circuit complexity, and matching resisted improvement for decades. Razborov proved in 1985 that computing matching requires monotone circuits of size nΩ(log⁡n)n^{\Omega(\log n)}nΩ(logn). That bound stood until Cavalar, Göös,…

16 thms2 active usersReviewed
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry·Captain: mikedeng1

Strong Lower Bounds for Weak Epsilon-NetsResearch Paper

A collection of regions often has to be met by a small set of representative points. In discrete geometry this is a piercing problem: every region must contain at least one chosen point. When the regions are convex and each contains a prescribed fraction of a finite input set, the minimum required number of representatives is the weak epsilon-net problem.…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Pareto Inefficiency of EFXResearch Paper

Dividing indivisible goods asks for a complete assignment of objects to people whose preferences may differ. A fair assignment should limit envy, while an efficient assignment should avoid a redistribution that benefits someone without harming anyone else. These requirements address different concerns. A participant can regard an allocation as unfair even…

13 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

At What Cost? (In)efficiency in First-Price Procurement AuctionsResearch Paper

A first-price procurement auction purchases one good or service by asking suppliers to submit prices simultaneously. The supplier quoting the lowest price wins and receives that price. A buyer concerned with productive efficiency cares about the selected supplier's actual cost, rather than the payment alone. The two can differ because suppliers bid…

19 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryInformation Theory·Captain: mikedeng1

The Multiple Unicast Conjecture is FalseResearch Paper

A multiple unicast instance models several independent communications sharing the same network. Each session has its own source and destination, and each connection has a capacity that must be shared by the sessions using it. Traditional routing sends each packet along a path, allowing a session to divide its traffic among several paths. Network coding also…

16 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Testability of General Graphs with Weak Query OraclesResearch Paper

A graph property tester examines a small part of a graph and distinguishes graphs having a property from graphs requiring many changes to acquire it. Researchers studying sublinear graph algorithms need to know which properties admit a query bound independent of the number of vertices. That question depends on what a query reveals. An adjacency query can…

23 thms2 active usersReviewed
Computational ComplexityConvex OptimizationQuantum Information+1·Captain: mikedeng1

Quantum lower bounds for convex optimization and real matrix-vector query problemsResearch Paper

Convex optimization asks for a feasible point whose objective value is close to the smallest feasible value. When the objective is available only through queries, the number of queries describes how much information an algorithm needs about an unknown function. Quantum algorithms can query superpositions of points, so a classical query lower bound does not…

30 thms2 active usersReviewed
🏆Completed
Graph TheoryInformation TheoryProbability·Captain: mikedeng1

Entropy Bounds for Local Coordination and Graph AmenabilityResearch Paper

Consider players on a graph who each output a random bit and want neighbours to agree, while each player sees only some of the available random sources. Hutchcroft, Rospuskova and Tamuz studied this problem for communication limited to a graph distance, and showed that low inefficiency forces the graph to be amenable: a small fraction of the edges can be…

14 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Algorithmic thresholds for finding large independent sets in random graphsResearch Paper

In a binomial random graph Gn,pG_{n,p}Gn,p​ the largest independent set has size about 2log⁡1/(1−p)(np)2\log_{1/(1-p)}(np)2log1/(1−p)​(np), while simple greedy procedures find one of size about half of that. Karp asked in 1976 whether an efficient algorithm can do better, and the question remains open. Since an unconditional answer is out of reach, current work asks which classes of algorithms can…

22 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Weakly Stable Roommates with Two Master Lists: Tractable Existence and Hard OptimizationResearch Paper

A roommates matching partitions a population into pairs. Each person ranks possible partners, and a proposed arrangement is stable when no two people both strictly prefer one another to their assigned partners. Preferences may contain ties. A person who is indifferent does not participate in a blocking pair on that comparison. This distinction matters when…

28 thms2 active usersReviewed
Graph TheoryProbability·Captain: mikedeng1

Exact Fully Dynamic Single-Source Shortest Paths in Nonnegative Weighted GraphsResearch Paper

Single-source shortest paths (SSSP) with nonnegative arc weights is a basic primitive of routing, navigation and graph analytics. In many applications the graph changes one arc at a time, and recomputing all distances with Dijkstra's algorithm in O(m+nlog⁡n)O(m+n\log n)O(m+nlogn) time (Fredman–Tarjan 1987) after every change discards the fact that most distances are unaffected.…

26 thms2 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Online Service with Per-Batch Maximum DelaysResearch Paper

Online routing with waiting costs asks when a server should act and which requests it should serve together. The objective changes substantially when a service event pays only its oldest request's waiting time. Adding a younger request to that event can increase its movement cost without increasing its delay charge. Researchers studying online routing and…

22 thms2 active usersReviewed
Functional AnalysisMarkov ChainProbability·Captain: mikedeng1

Spectral gaps of Hit-and-Run and Coordinate Hit-and-RunResearch Paper

A uniform sampler produces random points whose probabilities are proportional to volume inside a prescribed region. This is a basic operation in randomized integration and volume computation. For a region described by constraints, a sampling step can be simple even when drawing an independent uniform point is difficult. The relevant question is how quickly…

19 thms2 active usersReviewed
Combinatoricscryptography·Captain: mikedeng1

The Authentication Complexity of Byzantine ConsensusResearch Paper

Byzantine agreement (BA) asks nnn parties, each holding an input bit, to output a common bit despite up to ttt parties behaving arbitrarily, with the common output equal to the honest parties' input whenever those inputs coincide. It is a building block of state-machine replication and secure multiparty computation. Its resilience depends on the initial…

25 thms2 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

Private Uniform Language GenerationResearch Paper

A generator observes examples from an unknown collection of valid objects and must produce new valid objects. Uniform language generation asks for one finite sample bound that works for every target in a specified family. The objects can be finite strings, but their syntax plays no role: the model keeps only a countable universe and the subsets that count…

23 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: mikedeng1

Irreducibility for Topical MapsResearch Paper

A nonnegative matrix acts on vectors with nonnegative real coordinates. Its irreducibility condition identifies when interaction among the coordinates is sufficient to guarantee an eigenvector whose entries are all positive. Topical maps extend this setting to nonlinear functions that preserve order and positive scaling. Such functions occur in min-max…

5 thms2 active usersReviewed
🏆Completed
Complexity TheoryProbability·Captain: mikedeng1

Parallel Repetition for k-Player XOR GamesResearch Paper

Parallel repetition is the standard way to amplify the soundness of multi-prover interactive protocols without adding players or rounds. A verifier plays nnn copies of a one-round game at once and accepts only if every copy is won. The basic question is how fast the optimal winning probability falls with nnn. This matters for probabilistically checkable proofs…

15 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Optimal Truthful Approximation for House Allocation and Rank-Maximal Matchings with TiesResearch Paper

In house allocation, agents rank objects and each agent can receive at most one object. A rule that chooses an allocation from reported rankings must account for the possibility that agents misreport. The mathematical question is how much allocation quality an incentive requirement necessarily costs. Zhang, Zhao, Xu, Xi and Zhao study this question both for…

24 thms2 active usersReviewed
PreviousPage 40 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