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.

1377 open missions

Missions

126–150 of 1377
Open1377Completed119All1496
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: Shuze Chen

Bayesian Optimal Stopping: Invincible Prophets and Achievable PhilosophersResearch Paper

In a prophet inequality a decision-maker sees rewards X1,…,XnX_1,\dots,X_nX1​,…,Xn​ one at a time, must accept or reject each on arrival, and may accept only one. The classical theory assumes the distributions are known and compares an online rule with the offline maximum OFF=E[max⁡tXt]\mathrm{OFF}=\mathbb E[\max_tX_t]OFF=E[maxt​Xt​] (Samuel-Cahn 1984, Correa et al. 2017). In many applications the…

19 thms4 active usersReviewed
CombinatoricsComplexity TheoryMarkov Chain+1·Captain: Shuze Chen

Single-Variable Connectivity in Random kkk-SATResearch Paper

Random kkk-SAT is the standard testbed for the geometry of solution spaces of random constraint satisfaction problems. Statistical-physics predictions describe a sequence of transitions as the clause density α=m/n\alpha = m/nα=m/n grows: below a clustering (reconstruction) threshold almost all solutions are expected to form one well-connected piece, above it the…

32 thms4 active usersReviewed
Computational ComplexityMathematical Logic·Captain: mikedeng1

Parallelism and Adaptivity in Student-Teacher WitnessingResearch Paper

A search procedure can receive useful information even when its first proposed answer is wrong. A Student–Teacher game makes this interaction explicit: a computationally limited student proposes answers, while an unrestricted teacher supplies certificates explaining failures. Researchers in computational complexity and bounded arithmetic use these games to…

55 thms4 active usersReviewed
CombinatoricsMarkov ChainProbability·Captain: mikedeng1

Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ(1+1/\mathrm{e})\Delta(1+1/e)Δ via Hidden Hard-Core ModelsResearch Paper

Sampling a uniformly random proper qqq-coloring of a graph is a basic task in theoretical computer science, discrete mathematics and statistical physics, and the Glauber dynamics is the simplest sampler for it: repeatedly pick a uniformly random vertex and recolor it with a uniformly random color absent from its neighborhood. A conjecture going back to Jerrum…

31 thms4 active usersReviewed
CombinatoricsMachine LearningProbability·Captain: mikedeng1

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's AlgorithmResearch Paper

An unknown Boolean formula can be observed through examples that satisfy it. The question here is how many such examples suffice to describe approximately the same distribution of solutions. This matters in learning structured distributions: the requested hypothesis is an explicit formula whose uniformly sampled solutions resemble the observations'…

29 thms4 active usersReviewed
Complexity TheoryGraph TheoryProbability·Captain: iris

Tight Non-Adaptive Query-Approximation Tradeoffs for Maximum Matching Size EstimationResearch Paper

Maximum matching is a benchmark problem for algorithms with limited access to their input. In the adjacency-list query model an algorithm cannot read the graph; it may only ask for the degree of a vertex or for the iii-th entry of its adjacency list. Outputting the edges of a constant-factor approximate matching in this model needs Ω(n2)\Omega(n^2)Ω(n2) queries…

64 thms4 active usersReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: iris

On derandomizing the line-point low-degree testResearch Paper

A low-degree test checks, by reading a function f:Fm→Ff : \mathbb F^m \to \mathbb Ff:Fm→F on a few points, whether fff is close to a polynomial of total degree at most kkk. The line-point test of Rubinfeld and Sudan picks a random line ℓ\ellℓ, reads fff on all of ℓ\ellℓ, and accepts if f∣ℓf|_\ellf∣ℓ​ is a univariate polynomial of degree at most kkk. Low-degree tests are the algebraic…

28 thms4 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Abelian Cayley High-Dimensional Expanders with Polylogarithmic DegreeResearch Paper

High-dimensional expanders (HDXs) are simplicial complexes, with triangles and higher faces as well as edges, whose local neighbourhoods are expander graphs. Random walks on their faces mix rapidly, and they underlie sparse agreement tests, new PCPs, locally testable codes and quantum LDPC codes (Mao, arXiv:2609.08937, Section 1). The notion behind…

53 thms4 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

A Dichotomy for Terminal CyclabilityResearch Paper

Hamiltonian Cycle asks whether a graph has a cycle through all of its vertices. It is on Karp's list of NP-complete problems (Karp 1972) and stays NP-complete on planar graphs (Garey–Johnson–Tarjan 1976). Within minor-closed graph classes this gives a clean dichotomy: the problem is NP-complete on every minor-closed class containing all planar graphs, while…

46 thms4 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory+1·Captain: mikedeng1

A Deterministic Polynomial Kernel for Odd Cycle TransversalResearch Paper

An odd cycle transversal of a finite undirected graph is a set of vertices whose deletion leaves a graph that can be coloured with two colours, with adjacent vertices receiving different colours. The associated decision problem asks whether at most kkk deletions suffice. It is a basic example in parameterized graph algorithms: the graph may be large even when…

24 thms4 active usersReviewed
CombinatoricsComplexity TheoryLinear algebra·Captain: mikedeng1

Parity Decision Trees of Depth O(4dlog⁡∥f^∥1)O(4^d \log \| \widehat f \|_1)O(4dlog∥f​∥1​) for Boolean Functions fff of F2\mathbb F_2F2​-Degree dddResearch Paper

A parity decision tree computes a Boolean function by adaptively asking for the parity of selected input bits. This model allows a linear question to inspect many coordinates at once. It is useful in studying XOR communication problems: Alice knows a binary vector xxx, Bob knows a binary vector yyy, and both must determine f(x+y)f(x+y)f(x+y). A parity query about the sum…

23 thms4 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Reed–Muller Codes are Optimal Binary Linear 3-Query LCCsResearch Paper

A locally correctable code stores a message redundantly so that a requested symbol of its encoding can be recovered by reading only a few positions, even after an adversary changes a prescribed fraction of the stored word. The question concerns the amount of redundancy required by that local access guarantee. Reading the entire word would permit ordinary…

24 thms4 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: mikedeng1

Submodularity Is Barely TestableResearch Paper

A value oracle returns the value of a set function at a requested subset. Algorithms using such an oracle often rely on a global mathematical promise while observing only a small fraction of the function's values. Submodularity testing asks how much information is needed to check one such promise: diminishing marginal returns. This matters when a guarantee…

28 thms4 active usersReviewed
Graph Theory·Captain: mikedeng1

Using MSTs to Compute All-Pairs Mincuts and Beyond ...Research Paper

The all-pairs mincuts problem asks for a minimum cut separating each pair of vertices of an undirected graph. Gomory and Hu (Multi-terminal network flows, 1961) showed that for the capacity function n−1n-1n−1 cuts suffice and n−1n-1n−1 single-pair computations find them. Their structure rests on submodularity of the cut function.

25 thms4 active usersReviewed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

The Complexity of Nash Equilibrium in Network Congestion and Coordination GamesResearch Paper

Algorithmic game theory studies how to find stable outcomes when several decision makers interact. A Nash equilibrium is a profile of independent randomized choices in which no player can improve by changing their own choice. Network congestion games model players selecting routes whose costs increase with traffic. Network coordination games describe…

29 thms4 active usersReviewed
Complexity TheoryInformation TheoryProbability·Captain: mikedeng1

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy ConversionResearch Paper

A communication protocol lets two parties compute a function of inputs that they hold separately. Its messages can reveal information about those inputs, even when the answer itself is small. Researchers in communication complexity study this disclosure through information complexity: the least information that any correct protocol must reveal, with a…

25 thms4 active usersReviewed
Algorithmic Game TheoryComputational Complexity·Captain: mikedeng1

PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive ValuationsResearch Paper

Dividing land, a time interval, or another ordered resource can require each recipient's share to be connected. Envy-freeness asks that every agent value its own share at least as highly as anyone else's. Requiring connected shares makes the computational question different from unconstrained cake division: both the cuts and the assignment of the resulting…

25 thms4 active usersReviewed
Convex OptimizationProbability·Captain: mikedeng1

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear QueriesResearch Paper

A private query mechanism must balance the accuracy of its answers with the information it reveals about individual records. It also consumes randomness. When many queries are answered, generating the necessary independent random bits becomes a resource question of its own. Randomness complexity measures the expected number of unbiased bits consumed, in the…

22 thms4 active usersReviewed
Computational ComplexityProbability·Captain: mikedeng1

Online Algorithms Cannot Find Isolated Perceptron SolutionsResearch Paper

The binary perceptron asks for a vector of binary weights satisfying random linear inequalities. It is a model of learning with discrete weights and a test case for average-case computational complexity. Its geometry raises a specific algorithmic question: if most solutions have no nearby solutions, which solutions can an algorithm actually find? The pinned…

27 thms4 active usersReviewed
CombinatoricsComplexity TheoryProbability·Captain: mikedeng1

A Counting and Sampling Lovász Local Lemma IIResearch Paper

The Lovász Local Lemma (LLL) states that a family of rare bad events with few dependencies can be avoided simultaneously with positive probability. Applied to a constraint satisfaction problem, it says that a formula has a solution when every constraint is violated with small probability and shares variables with few others. The algorithmic LLL (Moser–Tardos…

24 thms4 active usersReviewed
Computational ComplexityLinear OptimizationOperations Research·Captain: mikedeng1

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problemsResearch Paper

An integer program asks for integer coordinates satisfying linear inequalities. Cutting planes strengthen the inequalities without removing integer solutions. A Chvátal–Gomory cut takes a valid inequality with integer coefficients and rounds its right-hand side down. The Chvátal closure is the set remaining after all such cuts are imposed once. A polyhedron…

43 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryMechanism Design·Captain: mikedeng1

On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated PriorsResearch Paper

A first-price auction awards a single item to a highest bidder and charges that bidder her own bid. Choosing a bid therefore involves predicting competitors' behavior. Researchers studying auction computation ask whether an equilibrium can be found efficiently from the publicly available description of bidders' information. The setting here allows their…

31 thms4 active usersReviewed
Quantum Information·Captain: mikedeng1

Distributed Quantum Certification with Clifford EncodersResearch Paper

A laboratory may need to verify that a device prepares a prescribed quantum state without learning a complete description of its output. Quantum state certification makes this a binary decision: accept the prescribed state and reject states separated from it by a specified distance. When independent copies are held in separate laboratories, communication…

29 thms4 active usersReviewed
Discrete GeometryNumber TheoryTheoretical Computer Science·Captain: iris

Exact SVP and CVP in Structured Lattices: Polynomial-Space Algorithms and ReductionsResearch Paper

The shortest vector problem (SVP) asks for a shortest nonzero vector of a lattice, and the closest vector problem (CVP) for a lattice vector nearest to a target. For general NNN-dimensional lattices the known 2O(N)2^{O(N)}2O(N)-time algorithms use exponential space (AKS01, MV13, ADRS15), while the fastest polynomial-space algorithms, enumeration in the line of Kannan…

40 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Quantum channel tomography: optimal bounds in the near-boundary regimeResearch Paper

Quantum channel tomography (also called quantum process tomography) asks for a full classical description of an unknown quantum channel, given black-box access to it. It is the standard way to certify gates and devices, and its query complexity is the basic sample-complexity question for learning quantum dynamics.

30 thms4 active usersReviewed
PreviousPage 6 of 56Next

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