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

1351–1375 of 1499
Open1321Completed178All1499
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious AdversaryResearch Paper

A multi-armed bandit models a learner that repeatedly chooses one of several actions while observing only the loss of the chosen action. The learner might have benefited from a different action, but the feedback does not reveal that action's loss. A standard benchmark is the best single arm in hindsight. A changing environment calls for a more flexible…

17 thms1 active userReviewed
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
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
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
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
CombinatoricsGraph Theory·Captain: mikedeng1

No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL ModelResearch Paper

A maximal independent set selects pairwise nonadjacent vertices so that every unselected vertex has a selected neighbor. Distributed algorithms use such sets to break symmetry and organize neighboring processors. The classical algorithms of Luby (1986) and Alon, Babai and Itai (1986) achieve logarithmic randomized round bounds. The pinned submission asks…

21 thms1 active userReviewed
Complexity TheoryDiscrete GeometryOperations Research+2·Captain: mikedeng1

4-Block Integer Programming is in FPTResearch Paper

An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…

14 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

An Ω~(log⁡nlog⁡m)\tilde \Omega(\log n \log m)Ω~(lognlogm) Information-Theoretic Lower Bound for Randomized Online Set CoverResearch Paper

A set cover selects sets whose union contains every required element, while minimizing the number selected. In its online version, requirements arrive over time and each must be covered immediately. A choice that looks economical on one prefix may prove unnecessary once more requirements arrive, but purchases cannot be reversed. The problem therefore…

10 thms1 active userReviewed
Graph TheoryProbability·Captain: mikedeng1

Two choices suffice: kkk-out sampling leaves O(n/k)O(n/k)O(n/k) intercomponent edges for k≥2k\geq 2k≥2Research Paper

Random kkk-out sampling sparsifies a graph by local choices: every vertex independently picks kkk of its incident edges. The question is how much connectivity information the sample loses, measured by the number of original edges that join distinct components of the sample. Contracting each sampled component leaves exactly these edges, and adding them to a…

17 thms1 active userReviewed
CombinatoricsComplexity TheoryProbability·Captain: mikedeng1

Metric Testing: A Characterization of One-Sided TestabilityResearch Paper

A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…

25 thms1 active userReviewed
PreviousPage 55 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin147148
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8DUducloc980
9BOBoomShaKaLaaaKa93100
10GAgaryholm900

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