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.

118 completed missions

Missions

26–50 of 118
Open1378Completed118All1496
🏆Completed
CombinatoricsComplexity Theory·Captain: mikedeng1

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous MessagesResearch Paper

Secure distributed computation asks parties to disclose enough information to evaluate a function while limiting what the evaluator can learn about their individual inputs. In the private simultaneous messages model, the parties share randomness hidden from the evaluator, each sends one message, and the evaluator recovers the answer. Even when each party…

30 thms4 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Faster Deterministic Distributed Matching: Breaking the Log-Squared BarrierResearch Paper

A matching is a set of graph edges with no shared endpoint. It represents simultaneous pairings of neighboring processors: every processor can participate in at most one selected interaction. A maximum cardinality matching selects as many edges as possible. In a distributed network, the difficulty is finding a large matching while each processor learns…

31 thms4 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Two ReLU layers is all you needResearch Paper

The architecture of a neural network limits which functions it can compute. For a rectified linear unit, or ReLU, the scalar activation is t↦max⁡(0,t)t\mapsto\max(0,t)t↦max(0,t). A question about exact expressivity asks whether additional hidden layers permit new functions when each layer may have arbitrary finite width. This question differs from approximation on a compact…

35 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel SchedulingResearch Paper

A machine that performs one task each day may need to revisit several tasks indefinitely. Pinwheel scheduling asks whether all required revisit frequencies can be met by a single daily assignment. The requirement concerns every consecutive block of days: a good long-run average alone does not prevent a task from waiting too long. This distinction makes the…

948 thms4 active usersReviewed
🏆Completed
Algebraic GeometryComplexity TheoryLinear algebra·Captain: mikedeng1

A Quadratic Lower Bound on Determinantal ComplexityResearch Paper

Determinantal representations are a basic model of algebraic computation. Valiant showed that every polynomial has one and made the size of the smallest such representation central to algebraic complexity, where proving a superpolynomial bound for the permanent is the algebraic analogue of P versus NP (Valiant 1979). Even super-linear bounds in the number…

20 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

A 2.81n2.81^n2.81n upper bound on the number of stable matchingsResearch Paper

A stable matching instance has nnn men and nnn women, each ranking the other side strictly. Gale and Shapley showed that a stable matching always exists (1962). How many there can be is a question Knuth posed in 1976, and it is listed among the open problems of Gusfield and Irving (1989), Manlove (2013) and Cechlárová, Cseh and Manlove (2019). The answer…

25 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: iris

Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and GeometryResearch Paper

In a linear bandit a learner repeatedly picks an action AtA_tAt​ from a known set A⊂Rd\mathcal A\subset\mathbb R^dA⊂Rd and observes only a noisy scalar loss YtY_tYt​ with mean At⊤θtA_t^\top\theta_tAt⊤​θt​. Linear bandits model sequential decisions with structured feedback: routing, recommendation, pricing, and experimental design. Two benchmarks are classical. Against an adversarial envi…

68 thms4 active usersReviewed
🏆Completed
Computational ComplexityQuantum InformationTheoretical Computer Science·Captain: iris

Randomized query complexity can beat certificate complexityResearch Paper

Query complexity measures how many input bits an algorithm must read to evaluate a Boolean function f:{0,1}N→{0,1}f:\{0,1\}^N\to\{0,1\}f:{0,1}N→{0,1}. For total functions (defined on every input) the classical, randomized and quantum measures are polynomially related, and a large part of the field consists of pinning down the best exponents in these relations; see the survey of…

39 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra+1·Captain: Shuze Chen

A Sharp Rigidity Law for Effective ResistanceResearch Paper

Effective resistances summarize a weighted graph as an electrical network: the resistance RuvR_{uv}Ruv​ between two vertices is the voltage needed to send one unit of current from uuu to vvv. They govern commute times and are the sampling probabilities of spectral sparsification (Spielman–Srivastava 2011), and they form a metric on the vertices.

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

Robust Shattering ArgumentsResearch Paper

Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set BBB of unresolved nodes, and the analysis has to show that…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: Shuze Chen

A Better-than-2 Approximation for k-MedianResearch Paper

In uncapacitated facility location (UFL) one opens a set of facilities, each at a cost, and connects every client to its nearest open facility. In k-median one opens at most kkk facilities and pays only connection costs. The two problems are linked by a Lagrangian relaxation: replacing the constraint ∣S∣≤k|S|\le k∣S∣≤k by a penalty f⋅∣S∣f\cdot|S|f⋅∣S∣ turns k-median into UFL…

25 thms3 active users
🏆Completed
AlgebraComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

PIT and Reconstruction for Sums of High PowersResearch Paper

Polynomial identity testing (PIT) asks whether a polynomial given by an arithmetic circuit is identically zero. In the black-box version the algorithm may only evaluate the polynomial at points of its choice, and a deterministic black-box algorithm is the same thing as a hitting set: a fixed finite set of points at which every nonzero polynomial of the…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Linear Hashing Is PoissonesqueResearch Paper

Hashing assigns a collection of objects to bins. Expected bin loads matter when the cost of an assignment depends on unusually crowded bins, or when nearly empty groups signal uneven coverage. A linear hash function assigns binary vectors using a matrix over the two-element field. Such maps have a concise algebraic description, but their outputs are…

26 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: Shuze Chen

Fatness and FlatnessResearch Paper

The theory of sparsity of Nešetřil and Ossona de Mendez describes the algorithmically useful structure of sparse graph classes. Its central notion, nowhere denseness, has many equivalent definitions. Two of them matter here. The first says that, for every radius rrr, contracting disjoint connected subgraphs of radius at most rrr cannot produce arbitrarily large…

20 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability+1·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Algebraic GeometryCombinatorics·Captain: mikedeng1

Toward Algebraic Geometry of Fixed-Parameter Tractability: Case StudiesResearch Paper

A hitting set selects vertices so that every input hyperedge contains a selected vertex. In the parameterized problem, the question is whether a hitting set of size at most a given number kkk exists. Even when a small solution exists, the collection of feasible solutions can be large. For algorithms that retain possible certificates, the relevant question is…

11 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Polynomial Lower Bounds for Steiner Shortcuts via Test FunctionsResearch Paper

A directed reachability query asks whether a directed graph contains a path from one specified vertex to another. Many algorithms first add edges to reduce the number of edges that such a path needs. This matters in parallel and distributed computation because a path requiring many successive steps can force many rounds of communication or dependent work.…

24 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
🏆Completed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

Anticoncentration of the Permanent in Ginibre EnsemblesResearch Paper

The permanent of an n×nn\times nn×n matrix, per⁡A=∑σ∈Sna1σ(1)⋯anσ(n)\operatorname{per}A=\sum_{\sigma\in S_n}a_{1\sigma(1)}\cdots a_{n\sigma(n)}perA=∑σ∈Sn​​a1σ(1)​⋯anσ(n)​, is the determinant without signs. Computing it exactly is #P-hard, and its behaviour on random Gaussian matrices sits at the centre of the complexity-theoretic case for quantum advantage in BosonSampling. Aaronson and Arkhipov (AA13) reduced…

23 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

The Local Query Complexity of Greedy Coloring and Other Extendable Labeling ProblemsResearch Paper

A graph may be too large for an application to construct and store a complete solution before answering its first question. A local computation algorithm instead answers questions about individual vertices through queries to the underlying graph. Its answers must remain consistent with one solution of the whole graph. The relevant resource here is the…

23 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability+1·Captain: mikedeng1

Approximate Counting of kkk-Paths in O∗(2k)O^*(2^k)O∗(2k) TimeResearch Paper

A directed kkk-path in a directed graph is an ordered tuple (v1,…,vk)(v_1,\dots,v_k)(v1​,…,vk​) of pairwise distinct vertices in which every consecutive pair (vi,vi+1)(v_i,v_{i+1})(vi​,vi+1​) is an arc. Deciding whether a kkk-path exists is a benchmark problem of parameterized algorithms, while counting kkk-paths exactly is #W[1]-hard for directed and undirected graphs (Flum–Grohe 2004). Approximate…

46 thms3 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

A Width Hierarchy of Monotone Algebraic Branching ProgramsResearch Paper

Algebraic complexity studies how much arithmetic is needed to produce a polynomial from its variables and constants. A monotone computation uses only nonnegative coefficients, so terms cannot disappear by cancellation. This restriction makes resource lower bounds accessible while retaining models that distinguish addition, multiplication, and reuse of…

22 thms3 active usersReviewed
🏆Completed
Graph TheoryInformation TheoryProbability·Captain: mikedeng1

Entropy-Weighted Soundness for Multi-Answer Birthday GraphsResearch Paper

A collection of small partial assignments can encode a complete satisfying assignment: retain every restriction of that assignment to a fixed number of coordinates. The converse question asks whether a comparably large collection of local assignments can be densely compatible when no global assignment satisfies most constraints. This question concerns the De…

34 thms3 active usersReviewed
PreviousPage 2 of 5Next

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