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

1326–1350 of 1496
Open1374Completed122All1496
CombinatoricsGraph Theory·Captain: mikedeng1

FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence PatternsResearch Paper

A hypergraph records a finite collection of constraints by assigning each constraint the set of variables it involves. In database query evaluation and constraint satisfaction, the shape of these overlaps can determine which decomposition methods are available. Different notions of width measure different freedoms in choosing a decomposition. Fractional…

22 thms1 active userReviewed
AlgebraComplexity TheoryComputational Complexity·Captain: mikedeng1

Factor Closure in Noncommutative Algebraic ComplexityResearch Paper

A basic structural question in algebraic complexity is whether factors of a polynomial with a small circuit also have small circuits. In the commutative setting small-circuit bounds for factors were established by Kaltofen ([10]), closure of commutative VNP in characteristic zero and sufficiently large characteristic was proved by Chou, Kumar and Solomon…

19 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

A Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper

A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…

17 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Testing Implies Distance Estimation with Polynomial LossResearch Paper

An adjacency query reveals one bit of a graph: whether two specified vertices share an edge. When the graph is large, even reading its entire adjacency matrix can be prohibitive. Property testing asks whether a graph satisfies a specified condition or requires a substantial fraction of its adjacencies to be changed. Distance estimation asks for that…

16 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Breaking the Parity Barrier for Constant-Depth CircuitsResearch Paper

A Boolean circuit computes a bit by combining input bits through logical gates. Circuit complexity asks how many gates a specified function needs when its depth is restricted. Lower bounds separate computational resources even when the function itself is easy to evaluate. For circuits using AND and OR gates with unrestricted fan-in, parity has long provided…

36 thms1 active userReviewed
Markov ChainProbability·Captain: mikedeng1

Learning AI Agents, Market Makers, and Stress in Automated MarketsResearch Paper

Two markets can exhibit the same distribution of individual returns while arranging losses differently in time. For a monitor concerned with consecutive losses, the duration of a stressed interval is a separate object from the frequency of stressed periods. The question here is whether this distinction survives a model in which trades respond to the…

5 thms1 active userReviewed
cryptographyTheoretical Computer Science·Captain: mikedeng1

Byzantine Broadcast in O~(n2)\widetilde{O}(n^2)O(n2) CommunicationResearch Paper

A replicated service needs a precise rule for turning one participant's proposed bit into a common decision. Byzantine broadcast asks for such a rule even when faulty participants can send inconsistent messages, omit messages, or change their behavior after being corrupted. The receiver of a message cannot infer that other parties received the same message.…

26 thms1 active userReviewed
Graph TheoryProbability·Captain: mikedeng1

Adaptive Steps and Certificates for Semi-Streaming Shortest PathsResearch Paper

A graph can have too many edges to keep in memory while its vertices and a sparse collection of edges still fit. In the semi-streaming model, an algorithm reads an insertion-only stream repeatedly and keeps a small working memory between scans. For shortest paths, the number of complete scans is a substantial part of the cost. Assadi, Hoppenworth and…

12 thms1 active userReviewed
Computational Complexitycryptography·Captain: mikedeng1

On ZLIP: Combinatorial Structures and Reduction to √n-ZSVPResearch Paper

A lattice is the set of integer combinations of a finite collection of linearly independent vectors. Its geometry can be simple while its given coordinates conceal that simplicity. The lattices considered here are Euclidean rotations of the integer grid: they have an orthonormal basis, but the input supplies an arbitrary integer change of that basis.…

26 thms1 active userReviewed
Algebraic TopologyTheoretical Computer Science·Captain: mikedeng1

Self-stabilising approximate clock synchronisation requires linear timeResearch Paper

Distributed systems use logical clock ticks to coordinate rounds of communication. A self-stabilising protocol must recover even when transient faults leave every process in an arbitrary local state. A second requirement is tolerance of permanent failures while recovery proceeds. These requirements occur together: an event that corrupts stored state can…

19 thms1 active userReviewed
CombinatoricsProbability·Captain: mikedeng1

Fluid Limits and Upper Bounds for Randomized Greedy MatchingResearch Paper

A matching is a set of graph edges with no shared endpoint. Matching algorithms assign disjoint pairs when each participant can receive at most one partner. A local algorithm can build a matching without inspecting the whole graph, but its decisions can prevent later pairs from forming. The Modified Randomized Greedy algorithm, abbreviated MRG, introduces…

8 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Computing faster with a full memory: Catalytic algorithms break time-space lower boundsResearch Paper

A catalytic algorithm, introduced by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), has a small clean work tape and a large dirty work tape. The dirty tape starts with arbitrary content the algorithm cannot choose, and must be returned intact at the end. The original question was whether such memory helps at all, and the first answers concerned…

8 thms1 active userReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper

A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…

28 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

LOCAL LLL in poly(loglog n) RoundsResearch Paper

The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…

20 thms1 active userReviewed
Complexity TheoryProbability·Captain: mikedeng1

Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper

The hard-core model samples an independent set III of a finite graph with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣; at λ=1\lambda=1λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …

25 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

The Power of Simple Mechanisms: A Tight eee-Approximation for Gains from Trade in Matching MarketsResearch Paper

A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…

23 thms1 active userReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: mikedeng1

A King for Almost EveryoneResearch Paper

A collection of pairwise contests can have cyclic outcomes: one contestant defeats a second, the second defeats a third, and the third defeats the first. A useful substitute for a contestant who defeats everyone is a king: a vertex that reaches every other vertex either directly or through one intermediary. The question here concerns the information needed…

10 thms1 active userReviewed
AlgebraComplexity Theory·Captain: mikedeng1

Almost-Linear Modular Composition over Arbitrary Commutative RingsResearch Paper

Polynomial algorithms often need to substitute one polynomial into another while retaining only its remainder modulo a third polynomial. This operation is called modular composition. It describes evaluation in a polynomial quotient algebra, so it appears whenever an algebraic element is represented by a polynomial relation. Over finite fields it occurs in…

16 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper

Distributed systems can need to know how many participants they contain even when communication links change from round to round. Counting asks every participant to determine this number exactly and then stop. Without identifiers, equal messages need not originate from the same participant. Receiving a correct estimate is also different from having enough…

28 thms1 active userReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

Polynomially larger deletion codes by linear hashing of substring countsResearch Paper

An error-correcting code selects some words of a fixed length so that a receiver can distinguish the selected words after errors. Insertions and deletions change the positions of later letters, making recovery a synchronization problem as well as a problem of identifying changed symbols. Researchers studying communication and storage channels therefore ask…

31 thms1 active userReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Tight Bounds for Randomized Generalized k-Server on Uniform MetricsResearch Paper

The generalized kkk-server problem was introduced by Koutsoupias and Taylor (KT04) as a model of kkk heterogeneous servers, each moving in its own metric space, that must jointly answer requests naming one location per server. It contains the classical kkk-server problem, weighted kkk-server, and paging with heterogeneous cache slots as special cases, and it is a…

12 thms1 active userReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple AuctionsResearch Paper

A seller with several distinct items must decide both what to offer and how to price it. Even when there is only one buyer and the buyer values a collection by adding its item values, the seller can offer lotteries as well as deterministic bundles. The benchmark of an optimal truthful auction therefore includes many more choices than posting one price for…

25 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper

Scheduling systems often know a job's processing-time distribution before they know its realized duration. An adaptive policy chooses the next job after observing previous outcomes. For Bernoulli jobs, a job either completes immediately or occupies a machine for its full positive size. This isolates the scheduling risk created by a small probability of a…

25 thms1 active userReviewed
Formal VerificationMathematical LogicTheoretical Computer Science·Captain: mikedeng1

Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper

A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…

21 thms1 active userReviewed
Operations ResearchProbability·Captain: mikedeng1

Online carpooling against an oblivious adversaryResearch Paper

In the online carpooling problem (Fagin–Williams 1983), people share rides in pairs and each ride must immediately name one of the two as the driver; the goal is that nobody drives much more or much less than their fair share. In graph language, edges on nnn vertices arrive one at a time and must be oriented immediately, keeping the indegree minus outdegree…

15 thms1 active userReviewed
PreviousPage 54 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