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

1301–1325 of 1499
Open1321Completed178All1499
CombinatoricsGraph TheoryProbability·Captain: Shuze Chen

Fractional colorings of KrK_rKr​-free graphs with local demandsResearch Paper

Lower bounds on the independence number in terms of degrees are among the oldest themes of extremal graph theory. For triangle-free graphs, Ajtai, Komlós and Szemerédi proved α(G)=Ω(nlog⁡d/d)\alpha(G)=\Omega(n\log d/d)α(G)=Ω(nlogd/d) for average degree ddd, and Shearer sharpened this to α(G)≥nf(d)\alpha(G)\ge n f(d)α(G)≥nf(d) with the explicit function f(d)=(dlog⁡d−d+1)/(d−1)2f(d)=(d\log d-d+1)/(d-1)^2f(d)=(dlogd−d+1)/(d−1)2 (Shearer 1983), later to the…

29 thms1 active userReviewed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: iris

The Gap Between Average-Case and Worst-Case ComplexityResearch Paper

Impagliazzo's "five worlds" ([Imp95], Structure in Complexity Theory 1995) separate two questions that complexity theory cannot yet tell apart. Is NP\mathsf{NP}NP hard in the worst case, and is it hard on average, for instances drawn from an efficiently samplable distribution? In the world called Heuristica, every problem in NP\mathsf{NP}NP is easy on average, yet…

45 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Incremental Open Addressing Has No Time-Space TradeoffResearch Paper

Open addressing is the hash-table framework behind linear probing, quadratic probing, double hashing, Robin Hood hashing and cuckoo hashing. In the incremental (insert-only) setting, keys are inserted one after another into an initially empty array of nnn slots until a target load factor (fraction of occupied slots) is reached. For more than half a century…

23 thms1 active userReviewed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Improved Algorithms in the Random-Order Model: Knapsack, GAP, and BeyondResearch Paper

Online services allocate limited resources to requests arriving over time. Accepting a request earns value but uses capacity a later, more valuable request might have needed, and decisions cannot be revised. The simplest such model is online knapsack; the generalized assignment problem (GAP) extends it to several machines on which an item may have different…

16 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

From Bilateral Trade to Matching Markets: Sharp Gains from TradeResearch Paper

In a matching market, unit-demand buyers and unit-supply sellers with privately known values and costs are connected by a compatibility graph, and a platform or market maker must decide who trades with whom and at what prices. Myerson and Satterthwaite (MS83) showed that incentive compatibility, voluntary participation and budget balance already rule out…

38 thms1 active userReviewed
Information TheoryProbabilityQuantum Information+1·Captain: iris

Tight Information-Theoretic Threshold for Decoded Quantum Interferometry with Local Quantum DecodersResearch Paper

Decoded quantum interferometry (DQI) is a quantum algorithm for sparse constraint problems such as Max-kkk-XORSAT: it prepares a state whose amplitudes favour good assignments by reducing optimization to the decoding of a classical linear code (Jordan et al., Nature 2025). How well DQI does is therefore governed by how well that code can be decoded from the…

25 thms1 active userReviewed
AlgebraAnalysisComputational Complexity+1·Captain: Shuze Chen

Multiplying matrices via polynomials: operational asymptotic spectrum barrierResearch Paper

The exponent of matrix multiplication ωF\omega_{\mathbb F}ωF​ is the least τ\tauτ such that n×nn\times nn×n matrices over a field F\mathbb FF can be multiplied with O(nτ+o(1))O(n^{\tau+o(1)})O(nτ+o(1)) arithmetic operations; equivalently, it measures the growth of the tensor rank of the matrix multiplication tensor ⟨n,n,n⟩\langle n,n,n\rangle⟨n,n,n⟩. In October 2026 OpenAI announced a proof that …

15 thms1 active userReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: Shuze Chen

Precedence-Constrained Decision Trees and CoveringsResearch Paper

In the Optimal Decision Tree problem an unknown target hypothesis h∗h^*h∗ from a finite set HHH of nnn hypotheses must be identified by adaptively performing tests from a family TTT of mmm tests; each test partitions HHH and its reply reveals the block that contains h∗h^*h∗. The problem goes back to Garey and Graham (1974) and appears in medical diagnosis, troubleshooting…

23 thms1 active userReviewed
Algorithmic Game TheoryEconomicsMechanism Design+1·Captain: Shuze Chen

Otter: A Provably MEV-Resilient Automated Market Maker via Surplus RedistributionResearch Paper

An automated market maker (AMM) is a smart contract that holds reserves of two tokens XXX and YYY and trades with anyone along a fixed pricing curve. On a blockchain the trades of one block are sequenced by a builder, who may also insert trades of its own. Ordering power yields maximal extractable value (MEV): in a sandwich attack the builder buys before a…

18 thms1 active userReviewed
AnalysisCombinatoricsProbability+1·Captain: Shuze Chen

Inside the Critical Window of Random 2-SATResearch Paper

Random 2-SAT is the one case of random kkk-SAT whose satisfiability threshold and scaling window are both known. With nnn Boolean variables and mmm random 2-clauses, a formula is satisfiable with probability tending to one when m/n<1m/n<1m/n<1 and unsatisfiable with probability tending to one when m/n>1m/n>1m/n>1, a result proved independently by Chvátal and Reed (FOCS 1992), Goerdt…

22 thms1 active userReviewed
CombinatoricsGraph TheoryOptimization+1·Captain: Shuze Chen

Better Bounds for Semi-Streaming Maximum Matching via Load BalancingResearch Paper

Graphs too large to store are often processed as a stream: the edges arrive one at a time, in an order nobody controls, and an algorithm may read the stream a few times (passes) while keeping only a small summary in memory. The semi-streaming model of Feigenbaum, Kannan, McGregor, Suri and Zhang (FKM+05) allows O~(n)=O(n⋅polylog n)\tilde O(n)=O(n\cdot\mathrm{polylog}\,n)O~(n)=O(n⋅polylogn) bits…

24 thms1 active userReviewed
Information TheoryOperations ResearchProbability+1·Captain: Shuze Chen

Eliminating Ongoing Interaction in Long-Running Verification AgentsResearch Paper

A long-running verification agent completes a chain of tasks, each of which must be submitted exactly, and it can consult a human expert along the way. Every consultation is paid, and every experiment the agent runs on its own tools is paid. A basic design question is whether the expert must stay available throughout the run, answering questions as they…

21 thms1 active userReviewed
CombinatoricsOperations ResearchProbability+1·Captain: Shuze Chen

Optimal Online Stochastic MatchingResearch Paper

In online bipartite matching, mmm offline vertices are known in advance and online vertices arrive one at a time, each revealing its neighbourhood; every arrival must be rejected or irrevocably matched to an unmatched neighbour, and the goal is a large matching. Under adversarial arrivals the Ranking algorithm of Karp, Vazirani and Vazirani is optimal with…

27 thms1 active userReviewed
CombinatoricsComplexity TheoryHarmonic Analysis+2·Captain: Shuze Chen

Low Soundness Linearity Testing on Subsets of the HypercubeResearch Paper

A linearity test reads a function f:F2n→F2f:\mathbb F_2^n\to\mathbb F_2f:F2n​→F2​ at a few random points and accepts or rejects. It is perfectly complete if it always accepts linear functions. It has low soundness if, whenever it accepts with probability at least (1+δ)/2(1+\delta)/2(1+δ)/2, fff agrees with an affine function on at least a (1+s(δ))/2(1+s(\delta))/2(1+s(δ))/2 fraction of inputs, with s(δ)>0s(\delta)>0s(δ)>0…

22 thms1 active userReviewed
Algorithmic Game TheoryEconomicsOperations Research+1·Captain: Shuze Chen

The Price of Anarchy in Markets for LemonsResearch Paper

Trade in a market for lemons can fail even when trade is efficient: when the seller knows more than the buyer about the quality of the good, a price at which the seller is willing to sell signals bad news to the buyer, and adverse selection can unravel the market (Akerlof 1970). Securities markets, used-asset markets and insurance all share this structure.…

19 thms1 active userReviewed
Linear algebraProbabilityRandom Matrix Theory+1·Captain: Shuze Chen

Random tensor isomorphism under orthogonal and unitary actions: Smoothed and average-case analysisResearch Paper

Two 3-tensors A,B∈Cn×n×nA,B\in\mathbb C^{n\times n\times n}A,B∈Cn×n×n are unitarily isomorphic when a change of orthonormal basis in each of the three modes turns one into the other. Deciding this, and its robust version (is BBB close to some basis change of AAA?), is the tensor analogue of comparing two matrices up to unitary equivalence. It arises in quantum information, where a…

19 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Finding Hypercliques Faster Than Brute ForceResearch Paper

A hypergraph is a collection of subsets of a vertex set, called edges. In a (k−1)(k-1)(k−1)-uniform hypergraph, every edge contains exactly k−1k-1k−1 vertices. A kkk-hyperclique consists of kkk vertices for which every (k−1)(k-1)(k−1)-subset is an edge. Checking each possible selection gives a running time of order nkn^knk. The algebraic question behind this mission asks whether the…

19 thms1 active userReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Estimating a Transition Point from Gibbs and Ground StatesResearch Paper

Learning a phase transition from a finite quantum system involves two independent choices: how many state copies to observe and how large a system each copy contains. A transition is defined by an infinite-volume limit, whereas every available density matrix belongs to a finite cube with a specified boundary. More copies refine information about that finite…

23 thms1 active userReviewed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Multi-Party Error Resilience beyond 1n\frac{1}{n}n1​Research Paper

An information dissemination task asks every participant in a communication network to learn every participant's input. This is a useful benchmark for adversarial communication: once a participant knows the full input vector, it can evaluate any specified function of those inputs locally. The distinction between learning all inputs and learning only the…

26 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Small classes have linear neighbourhood complexityResearch Paper

A graph class can be studied by counting how many of its graphs exist on a fixed set of labels. It can also be studied by counting the different adjacency patterns visible on a chosen vertex set inside one graph. These are different measurements: the first concerns a collection of whole graphs, while the second concerns local observations within an…

21 thms1 active userReviewed
Computational ComplexitycryptographyMathematical Logic+1·Captain: Shuze Chen

Fine-Grained Proof Complexity for Elementary Arithmetic in Extended FregeResearch Paper

Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…

18 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Byzantine Partition Detection Under ChurnResearch Paper

Byzantine fault-tolerant protocols are proved correct under two separate assumptions: a bound ttt on the number of faulty processes, and enough vertex connectivity in the communication network (classically, connectivity above a multiple of ttt). The second assumption is usually taken for granted. Sengupta and Perrin ask whether the participants themselves can…

25 thms1 active userReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: Shuze Chen

Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and ErasuresResearch Paper

Secure multi-party computation lets parties compute a joint function of private inputs while revealing nothing beyond the output. In the client–server setting, a few clients with inputs delegate the work to nnn servers that have no inputs, and an adversary may corrupt one client and a fraction α\alphaα of the servers. Oblivious transfer (OT) is the basic…

24 thms1 active userReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: iris

Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNPResearch Paper

A one-way function is an efficiently computable function f:{0,1}n→{0,1}mf : \{0,1\}^n \to \{0,1\}^mf:{0,1}n→{0,1}m that no efficient algorithm can invert on a random image: given y=f(x)y = f(x)y=f(x) for uniform xxx, it is hard to find any x′x'x′ with f(x′)=yf(x') = yf(x′)=y. One-way functions are the minimal assumption of private-key cryptography, and their quantitative strength, the best inversion probability an…

65 thms1 active userReviewed
Algorithmic Game TheoryGraph TheoryMechanism Design+1·Captain: iris

Pairwise Exchanges of Freely Replicable Goods with Negative ExternalitiesResearch Paper

Datasets, software and patents are freely replicable: giving a copy costs the giver nothing directly. Firms that hold such goods are often competitors, so each one gains from acquiring a good and loses when a rival acquires one. Data consortia and patent pools face this tension: every member wants access to the others' goods, and no member wants its rivals…

30 thms1 active userReviewed
PreviousPage 53 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin140143
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8DUducloc970
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