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

926–950 of 1496
Open1374Completed122All1496
🏆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
Machine LearningProbabilityStatistics·Captain: mikedeng1

Is Randomness Necessary for Adaptive Data Analysis?Research Paper

A dataset is often reused to answer questions chosen after seeing earlier answers. Each answer can influence the next question, so the usual guarantee for one question fixed in advance does not automatically extend to the resulting interaction. Adaptive data analysis asks what a mechanism can reliably reveal about a population from a single finite sample in…

13 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
CombinatoricsComputational ComplexityGraph Theory·Captain: mikedeng1

Triangle-Freeness: Estimation Is as Easy as TestingResearch Paper

An algorithm examining a large graph may have time to inspect only a small part of its adjacency matrix. Property testing asks whether the graph has a specified property or requires a substantial number of edge changes to acquire it. Distance estimation asks how many changes are needed, to a prescribed additive accuracy. For triangle-freeness, a tester can…

17 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
ProbabilityQuantum Information·Captain: mikedeng1

Near-Optimal Mixedness Testing with Pauli MeasurementsResearch Paper

An experimenter may need to determine whether a prepared quantum system is maximally mixed without reconstructing its entire state. The restriction on available measurements matters: measuring each qubit separately gives a different information budget from a measurement that jointly processes many qubits or many copies. Mixedness testing asks for a decision…

19 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
Graph Theory·Captain: mikedeng1

Quantitative Results on Super-Ramanujan GraphsResearch Paper

A ddd-regular graph always has ddd as its largest adjacency eigenvalue. How far the remaining eigenvalues stay from ddd measures how well the graph expands, and good spectral expanders are used throughout pseudorandomness, error-correcting codes, derandomization and the design of communication networks. The Alon–Boppana bound shows that for a fixed degree ddd the…

20 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
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
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
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Computing Weighted Set Covers with Heterogeneous Stochastic Oracles: Deadline-Constrained Token ComplexityResearch Paper

A weighted set cover instance consists of a finite universe of elements, a family of subsets whose union contains the universe, and a positive weight for each subset. A cover is a subfamily containing every element; its weight is the sum of its subset weights. A service that proposes a cover can be useful even when its answer is uncertain: the proposed…

16 thms2 active usersReviewed
cryptographyQuantum Information·Captain: mikedeng1

Anchoring the Security of Invariant Quantum MoneyResearch Paper

A public verifier lets anyone check a quantum banknote, while its security asks whether an efficient algorithm can turn one issued banknote into two accepted registers. For invariant quantum money, the banknote is a superposition of combinatorial objects sharing a public invariant. A classical description of one object therefore supplies useful information…

14 thms2 active usersReviewed
Quantum InformationQuantum Mechanics·Captain: mikedeng1

Scalable Passive QRAMResearch Paper

A quantum random access memory (QRAM) lets a quantum algorithm query classical data while its address is in superposition. Algorithms that assume such access need an implementation whose cost includes loading and retrieving the data. A device containing many components can still have a small cost per query: conventional memory changes only a small fraction…

25 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Sparsification of Gaussian ProcessesResearch Paper

A Gaussian process is a family of random variables whose finite subfamilies are jointly Gaussian. Its supremum describes the largest fluctuation across a collection of correlated measurements. In finite-dimensional geometry, the same construction gives support functions of convex sets and many norm representations. Knowing the expectation of such a supremum…

22 thms2 active usersReviewed
🏆Completed
AlgebraInformation Theory·Captain: mikedeng1

Limits of Finite-Sample Dependence Measures under Data Processing InequalityResearch Paper

A dependence measure assigns a number F(U)F(U)F(U) to the joint distribution UUU of two finite-valued random variables XXX and YYY. Two requirements are natural. The measure should vanish when XXX and YYY are independent, and it should obey the data processing inequality (DPI): passing XXX through a noisy channel cannot increase its dependence on YYY. Shannon mutual information…

20 thms2 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput MaximizationResearch Paper

Nonpreemptive throughput maximization is a basic real-time scheduling problem: a set of jobs, each available only during a time window, must be placed on identical machines so that as many jobs as possible finish by their deadlines. It models admission control in real-time systems and allocation of communication resources (Bar-Noy, Guha, Naor and Schieber,…

20 thms2 active usersReviewed
Computational ComplexityMachine Learning·Captain: mikedeng1

Spatial Communication Complexity of Agnostic Halfspace LearningResearch Paper

Moving data costs energy, and in a circuit the cost grows with the distance a bit travels. Grover's bit-meter measure charges every transmitted bit by the length of the wire it crosses (Grover 2015); with it, Blake and Kschischang proved that decoding positive-rate codes over a binary erasure channel with exponentially small block error probability needs …

23 thms2 active usersReviewed
PreviousPage 38 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