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.

178 completed missions

Missions

151–175 of 178
Open1321Completed178All1499
🏆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
🏆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
🏆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
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

Private Uniform Language GenerationResearch Paper

A generator observes examples from an unknown collection of valid objects and must produce new valid objects. Uniform language generation asks for one finite sample bound that works for every target in a specified family. The objects can be finite strings, but their syntax plays no role: the model keeps only a countable universe and the subsets that count…

23 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
🏆Completed
Complexity TheoryProbability·Captain: mikedeng1

Parallel Repetition for k-Player XOR GamesResearch Paper

Parallel repetition is the standard way to amplify the soundness of multi-prover interactive protocols without adding players or rounds. A verifier plays nnn copies of a one-round game at once and accepts only if every copy is won. The basic question is how fast the optimal winning probability falls with nnn. This matters for probabilistically checkable proofs…

15 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
🏆Completed
Harmonic AnalysisMachine Learning·Captain: mikedeng1

The Spectral Cost of Sharpness: Fourier Truncation, the Gibbs Bend, and the Computability of ClassificationResearch Paper

A classifier that is a finite Fourier sum cannot jump. Sharpness, meaning how quickly a classifier passes from confidently negative to confidently positive across a decision boundary, therefore has a price in bandwidth, the largest frequency it uses. Wenwei Li's manuscript The Spectral Cost of Sharpness (STOC 2027 submission #122) puts a number on that…

24 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

A Hitting Set Lemma for HDX & ApplicationsResearch Paper

The hitting set lemma for expander graphs bounds the probability that a random walk stays inside a fixed set of vertices: for a graph whose normalized second singular value is at most λ\lambdaλ and a set SSS of density μ\muμ, a (d−1)(d-1)(d−1)-step walk from a random vertex stays in SSS with probability at most μ(μ+λ)d−1\mu(\mu+\lambda)^{d-1}μ(μ+λ)d−1. Results of this type underlie…

29 thms2 active usersReviewed
🏆Completed
Complexity TheoryMathematical LogicTheoretical Computer Science·Captain: iris

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]\mathsf{AC}^0[2]AC0[2]-FregeResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR and parity (XOR) gates. Superpolynomial lower bounds for the corresponding circuit class have been known since Razborov and Smolensky (1987) (Razborov 1987, Smolensky 1987), but carrying these techniques over to proofs has been open since the 1990s (Be…

64 thms2 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryInformation Theory·Captain: iris

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear CodesResearch Paper

Hash-based succinct arguments (SNARKs) such as FRI-based and STIR/WHIR-style systems test that a committed word is close to a linear code. To keep proofs short, they test many words at once by testing a single random linear combination. This batching is sound when the code has the proximity-gaps property at radius ρ\rhoρ: if fff or ggg is far from the code CCC,…

31 thms2 active usersReviewed
🏆Completed
Graph TheoryProbabilityRandom Matrix Theory·Captain: iris

Rotating Walks, Derandomized Squares, and Permutation Conjugated WalksResearch Paper

An expander is a sparse graph whose random walk mixes quickly; for a ddd-regular graph on NNN vertices the quality is measured by λ(G)\lambda(G)λ(G), the largest magnitude of a non-trivial eigenvalue of the adjacency matrix. Expanders are used throughout theoretical computer science for derandomization, error-correcting codes and pseudorandom walks (Hoory–Linial–Wigders…

49 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOptimization·Captain: iris

Compensation DesignResearch Paper

Platforms that aggregate content or data, such as generative-AI answer engines, recommendation services and data marketplaces, depend on independent contributors who decide for themselves whether to take part. Each contributor bears a private cost of participating, and the platform has a fixed budget to distribute. The platform knows how much value any set…

41 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: iris

Rounding, Ranges, and Exact Sample-Removal Audits for Least SquaresResearch Paper

The sign of a least-squares coefficient often carries the substantive conclusion of an empirical study. Giordano, Meager and Broderick showed that deleting a small fraction of the observations can reverse such conclusions in prominent studies (GMB26). This raises an auditing question: how many observations must be removed before a conclusion drawn from an…

21 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Paths and Intersections: Repelling PairsResearch Paper

The distance realization problem asks, given a metric DDD on a finite set TTT of terminals and a family of graphs, whether some graph in the family with nonnegative edge lengths, possibly with extra Steiner vertices, has shortest-path metric exactly DDD on TTT. The question goes back to Hakimi and Yau (1965) and appears in phylogenetics, hierarchical classification…

38 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Stable Voting Rules on the Edge of Optimal Metric DistortionResearch Paper

An election asks a group to choose one candidate from rankings alone. The metric distortion framework of Anshelevich, Bhardwaj and Postl (2015) measures how much those rankings cost: voters and candidates are points of an unknown metric space, each voter ranks closer candidates higher, and a voting rule's distortion is its worst-case ratio between the…

53 thms2 active usersReviewed
🏆Completed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: iris

Fourier Entropy Bounds via ApproximationsResearch Paper

A Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1} has a unique Fourier expansion f=∑S⊆[n]f^(S)χSf=\sum_{S\subseteq[n]}\widehat f(S)\chi_Sf=∑S⊆[n]​f​(S)χS​, and by Parseval's identity the squared coefficients {f^(S)2}S\{\widehat f(S)^2\}_S{f​(S)2}S​ form a probability distribution on subsets of [n][n][n]. Its Shannon entropy, the Fourier entropy H(f^2)\mathbb H(\widehat f^2)H(f​2), measures how spread out the spectrum of fff is.

21 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Online Beck–Fiala Down to Logarithmic SparsityResearch Paper

The Beck–Fiala problem asks how well the columns of a sparse matrix can be balanced by signs: given vectors a1,…,aT∈[−1,1]na_1,\dots,a_T\in[-1,1]^na1​,…,aT​∈[−1,1]n, each with at most ddd nonzero coordinates, choose εt∈{−1,1}\varepsilon_t\in\{-1,1\}εt​∈{−1,1} so that ∥∑tεtat∥∞\|\sum_t\varepsilon_ta_t\|_\infty∥∑t​εt​at​∥∞​ is small. The conjectured answer, O(d)O(\sqrt d)O(d​) independently of nnn and TTT, is one of the central questions of…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryProbability+1·Captain: iris

Discrepancy for Random Linear CodesResearch Paper

A random linear code of length nnn and dimension kkk over the finite field Fq\mathbb F_qFq​ is the column space of a uniformly random matrix G∈Fqn×kG\in\mathbb F_q^{n\times k}G∈Fqn×k​. Such codes serve as the default object against which explicit constructions in coding theory and pseudorandomness are measured. Many of their good properties are statements of the same kind: the…

28 thms2 active usersReviewed
🏆Completed
Complexity TheoryMathematical LogicTheoretical Computer Science·Captain: iris

Progress on AC0[2]-Frege Lower BoundsResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by…

36 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebraOperations Research+1·Captain: iris

The k-server conjecture is trueResearch Paper

The kkk-server problem, introduced by Manasse, McGeoch and Sleator in 1988 (MMS88), is the central problem of competitive analysis: kkk servers sit at points of a metric space, requests arrive one at a time at points of the space, and an online algorithm must move a server to each request before seeing the next one, minimizing the total distance travelled.…

31 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Concentration on HDX: Simplified and OptimizedResearch Paper

The Chernoff–Hoeffding bound says that the average of ddd independent [0,1][0,1][0,1]-valued variables deviates from its mean by more than α\alphaα with probability at most 2exp⁡(−2α2d)2\exp(-2\alpha^2d)2exp(−2α2d). High-dimensional expanders (HDX) are sparse hypergraphs whose hyperedges are far from independent, yet behave like independent samples in several ways. They have driven recent…

21 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic AlgorithmsResearch Paper

In online graph coloring the vertices of a graph arrive one at a time, each with its edges to the vertices that arrived earlier, and an algorithm must give every new vertex a color immediately and irrevocably, different from the colors of its neighbours. The problem models resource assignment under uncertainty (register allocation, frequency assignment,…

19 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: iris

High-dimensional expanders, the sparsest cut problem, and Steurer’s conjectureResearch Paper

The O(log⁡n)O(\sqrt{\log n})O(logn​)-approximation of Arora, Rao and Vazirani for the sparsest cut problem rests on a structural theorem about unit vectors satisfying the squared triangle inequality (ℓ22\ell_2^2ℓ22​ metrics): if such vectors are spread out, two linear-sized sets of them are Ω(1/log⁡n)\Omega(1/\sqrt{\log n})Ω(1/logn​) apart (ARV09). Barak, Raghavendra and Steurer showed that higher…

30 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning+1·Captain: iris

Calibeating Bandit AdviceResearch Paper

Many sequential decision systems already run a recommendation algorithm: a pricing heuristic, a statistical model trained on private data, a Q-learning agent. A downstream learner who receives its advice in each round may want two things at once. First, the learner should never regret having followed the advice blindly: whatever consistent re-mapping of the…

33 thms2 active usersReviewed
PreviousPage 7 of 8Next

Top contributors

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

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