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.

1347 open missions

Missions

1176–1200 of 1347
Open1347Completed152All1499
AlgebraCombinatoricsComplexity Theory+1·Captain: iris

Private PCPs from Product ExpansionResearch Paper

The PCP theorem says that the witness of an NP problem can be written as a proof that a verifier checks by reading a few random positions. Its quantum analogue for QMA is open. A main obstacle is local indistinguishability: a witness stored in a quantum code of distance ddd cannot be read from any d−1d-1d−1 positions, so local tests cannot tell a YES witness from a…

36 thms1 active userReviewed
CombinatoricsNumber TheoryProbability·Captain: mikedeng1

Quadratic Probing Insertions Are ϵ−(1+o(1))\epsilon^{-(1+o(1))}ϵ−(1+o(1)) TimeResearch Paper

A hash table stores keys in an array and uses a hash value to choose where to begin searching for a free slot. Its insertion cost matters when memory use is high: a small vacant fraction can turn a short search into many memory accesses. Quadratic probing searches at square offsets from the hash. Introduced by Maurer in 1968, it has a long history of use,…

26 thms1 active userReviewed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Caching with a Changing Cache SizeResearch Paper

Most of caching theory assumes a cache of fixed size, but real caches change size over time: a processor's last-level cache is repartitioned among cores at runtime, and a virtual machine's memory is reclaimed and regranted by its host. Cache-adaptive analysis studies algorithms on such caches, and it relies on one comparison: how much more memory and speed…

24 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Parity and Pattern Detection in Permutation StreamsResearch Paper

In the permutation streaming model the input π1,…,πn\pi_1,\dots,\pi_nπ1​,…,πn​ is promised to be a permutation of [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, its values arrive one at a time, and an algorithm must decide a property of the permutation with as little memory as possible. The promise removes every problem that is invariant under reordering, so what remains are questions about the order…

15 thms1 active userReviewed
Machine LearningStatistics·Captain: mikedeng1

An Optimal Agnostic PAC AlgorithmResearch Paper

Binary classification from i.i.d. examples is the basic model of statistical learning theory, and the sharp sample complexity of learning a class of finite VC dimension has been studied since the work of Vapnik and Chervonenkis and of Valiant. The question matters to learning theorists because it decides how much data a learner needs when the best…

15 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

The Quantumly Fast and the Classically ForriousResearch Paper

The Forrelation problem was introduced by Aaronson (STOC 2010) as a query problem that separates quantum from classical computation as strongly as possible. Two Boolean functions χf,χg:F2n→{−1,1}\chi_f,\chi_g:\mathbb F_2^n\to\{-1,1\}χf​,χg​:F2n​→{−1,1} are given as black boxes, and the task is to decide whether χg\chi_gχg​ is correlated or anticorrelated with the Fourier transform of χf\chi_fχf​. A…

19 thms1 active userReviewed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Minimax Alternating Regret for the Experts Problem and Online Convex OptimizationResearch Paper

Alternating regret measures an online learner using both its action before a loss is revealed and its next action, chosen after seeing that loss. This timing arises when two players update their strategies alternately: one response is evaluated against two successive states of the opponent. Researchers studying online learning and game dynamics therefore…

17 thms1 active userReviewed
Complexity TheoryGraph TheoryProbability·Captain: mikedeng1

A Fully Polynomial Randomized Approximation Scheme for Hypergraph UnreliabilityResearch Paper

Network unreliability quantifies the risk that independent component failures disconnect a system. A hyperedge models one component connecting a whole set of vertices, so one failure can remove a connection among arbitrarily many endpoints. All-terminal unreliability is the probability that the surviving hypergraph has more than one connected component. The…

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

Subset Sum via Partial MatchResearch Paper

Subset sum is a basic NP-complete problem and a standard test case for exact exponential algorithms: given integers and a target, decide whether some subset sums to the target. For more than fifty years the best worst-case running time had exponent n/2n/2n/2, and whether that exponent can be lowered by any constant was a long-standing open question.

26 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

The Online Steinitz ProblemResearch Paper

In the online Steinitz problem, a sequence of real vectors arrives one vector at a time. Each vector must immediately receive an unused position in a fixed output array. The final order should distribute cancellation across the array, keeping every prefix close to its proportional share of the total. This differs from choosing a permutation after seeing the…

17 thms1 active userReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Breaking the √3 Barrier for Maximum Weighted 3-Set PackingResearch Paper

A weighted 3-set packing instance describes requests that each use at most three resources. Two requests can be accepted together exactly when their resource sets are disjoint. Their values need not be equal or comparable in magnitude. The objective is to choose compatible requests with maximum total value. This setting includes weighted three-dimensional…

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

The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in ThreeResearch Paper

Majority is the Boolean decision that accepts an input when at least half its variables are one, accepting ties. Its description is short, but the size of a circuit implementing it depends substantially on the permitted gates and depth. For a fixed architecture, an exponential upper and lower bound can still leave an exponential gap if their bases differ.…

22 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
PreviousPage 48 of 54Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn691113
3SHshivm1630
4PAparclytaxel150172
5MTmartelus trismortuus1050
6GAgaryholm900
7WCwcysai8486
8A1a142857a7518
9SCSenrui Chen6757
10BEbersubs6574

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