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.

1378 open missions

Missions

1–25 of 1378
Open1378Completed118All1496
Complexity TheoryOperations ResearchOptimization·Captain: iris

The Computational Complexity of Avoiding Strict Saddle Points in Constrained OptimizationResearch Paper

Nonconvex optimization over a polytope, min⁡x∈Xf(x)\min_{x\in\mathcal X} f(x)minx∈X​f(x) with X={x∈Rd:Ax≤b}\mathcal X=\{x\in\mathbb R^d: Ax\le b\}X={x∈Rd:Ax≤b}, is the basic model behind constrained training problems and many operations-research formulations. Gradient methods reach first-order stationary points, but these include strict saddle points, which degrade solutions in practice. The usual remedy…

98 thms10 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Learning Finite Gaussian Location Mixtures via Gated Moments and Posterior CoversResearch Paper

A finite Gaussian location mixture in Rd\mathbb R^dRd is the law of X=μI+GX=\mu_I+GX=μI​+G, where the hidden index III takes the value iii with probability wiw_iwi​ and G∼N(0,Id)G\sim N(0,I_d)G∼N(0,Id​) is independent noise. Such mixtures are a basic model of heterogeneous data in statistics and machine learning. Distribution learning asks for a description of a law P^\hat PP^ close to the mixture PPP in…

28 thms8 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Optimal and Verifiable Quantum Advantages in Communication ComplexityResearch Paper

Communication complexity measures how many bits (or qubits) two parties, Alice and Bob, must exchange to solve a joint task when each sees only part of the input. It is one of the few settings where quantum advantages can be proved unconditionally, and such separations now underpin experimental demonstrations of quantum advantage in space (Kretschmer et al.…

39 thms7 active usersReviewed
Graph Theory·Captain: mikedeng1

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear SeparatorsResearch Paper

An independent set in a graph is a collection of vertices with no edge between any two selected vertices. With a rational value attached to each vertex, maximum weight independent set asks for the largest possible sum of selected values. This expresses selection problems in which edges represent pairwise incompatibility. The distinction between a graph and…

72 thms7 active usersReviewed
Quantum InformationRepresentation Theory·Captain: mikedeng1

Random dimension reduction and learning symmetric properties of quantum statesResearch Paper

A quantum state is a positive complex matrix of trace one. Its matrix entries depend on a basis, while quantities such as its eigenvalues do not. When several unknown states share a physical register, their relative eigenbases also contain information. Applying the same change of coordinates to every state preserves this relationship. Quantum learning tasks…

35 thms7 active usersReviewed
Algorithmic Game TheoryComplexity Theory·Captain: iris

Competitive Equilibrium for Linear Chores is CLS-completeResearch Paper

A Fisher market sells divisible items to agents who each hold a budget; a competitive equilibrium (CE) is a price vector at which every agent buys a best bundle she can afford and every item is sold. When the items are goods with linear utilities, equilibria are the optimal solutions of the convex Eisenberg–Gale program and can be computed in polynomial…

41 thms7 active usersReviewed
Computational ComplexityGraph TheoryQuantum Information+1·Captain: mikedeng1

The Complexity of Space–Reset Tradeoffs in Online Quantum ComputationResearch Paper

Quantum devices that process a stream of inputs — a quantum memory interleaved with arriving qubits, a sequential state generator, a device simulating a correlated noise process — keep a bounded private memory between time steps and remove information by irreversible operations such as qubit RESET. Both resources are limited on hardware: the number of…

37 thms6 active usersReviewed
Graph TheoryMarkov ChainTheoretical Computer Science·Captain: mikedeng1

Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower BoundsResearch Paper

A graph can contain a large well-connected subsystem even when the rest of the graph has no useful global structure. For a graph algorithm that only inspects a small portion of its input, recognizing the existence of such a subsystem differs from recognizing expansion of the whole graph. The subsystem might occupy forty percent of the vertices while the…

31 thms6 active usersReviewed
Quantum Information·Captain: mikedeng1

Near-optimal incoherent tomography of low-rank quantum channelsResearch Paper

A quantum channel describes how an input quantum system changes when it passes through a physical device. Learning that channel gives a classical description that can be used to compare devices, characterize noise, and predict their response to new inputs. The choice of experimental resources matters: a learner with quantum memory can combine several…

23 thms6 active usersReviewed
Computational ComplexityGraph TheoryProbability·Captain: mikedeng1

Testing MAX-CUT in the Adjacency Matrix Model: Tight Non-Adaptive Bounds and a Cubic Adaptive Lower BoundResearch Paper

A graph can encode a dense binary relation whose full adjacency matrix is too large to inspect. MAX-CUT estimation asks for the number of edges in a largest cut, up to additive error measured against the square of the vertex count. The output is a number; producing a corresponding partition is a different requirement. This estimation problem is one of the…

25 thms6 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Concentration from Product Moments via an Additional Element of RandomnessResearch Paper

Many randomized algorithms and constructions produce a sum ∑iYi\sum_i Y_i∑i​Yi​ of [0,1][0,1][0,1]-valued quantities, each computed from a few random bits that are shared with other summands. The read-Δ\DeltaΔ inequality of Gavinsky, Lovett, Saks and Srinivasan (Random Structures & Algorithms 2015) states that if each bit influences at most Δ\DeltaΔ of the YiY_iYi​ and the bits are…

30 thms6 active usersReviewed
CombinatoricsComplexity TheoryInformation Theory·Captain: Shuze Chen

Binary Huffman Coding with Unequal Letter Costs Is NP-CompleteResearch Paper

A binary prefix code assigns to each of NNN source symbols a word over {0,1}\{0,1\}{0,1} so that no codeword is a prefix of another, which makes concatenated codewords decodable without separators. For symbol frequencies w1,…,wNw_1,\dots,w_Nw1​,…,wN​, Huffman's 1952 greedy algorithm minimizes the weighted length ∑iwi∣Ci∣\sum_i w_i |C_i|∑i​wi​∣Ci​∣ in polynomial time (Huffman 1952). When the two letters…

25 thms6 active usersReviewed
Complexity TheoryInformation TheoryProbability·Captain: mikedeng1

Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz–Thompson EstimatorResearch Paper

A stored binary message can be protected by an encoding that expands it into a longer word. A locally decodable code aims to recover one requested message bit after reading only a few coordinates, even when part of the stored word has been corrupted. Its relaxed version permits the decoder to abort on corrupted words. On a valid codeword it must still…

31 thms6 active usersReviewed
CombinatoricsMachine LearningProbability+1·Captain: iris

Learning CNF Formulas with Uniform Random Solutions and Membership QueriesResearch Paper

A CNF formula Φ\PhiΦ on nnn Boolean variables defines a set of solutions Ω(Φ)\Omega(\Phi)Ω(Φ) and, when this set is nonempty, the uniform distribution μΦ\mu_\PhiμΦ​ on it. Learning Φ\PhiΦ from uniform random solutions asks for a formula Φ^\widehat\PhiΦ whose uniform solution law is close to μΦ\mu_\PhiμΦ​ in total variation. The question connects distribution learning, constraint…

37 thms6 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Best-of-Many-Worlds MMS Allocation for Chores with Sublinear DisposalsResearch Paper

Dividing undesirable tasks gives a cost to every recipient. A person asked to divide all tasks into equal shares may still be unable to find a share she considers acceptable once other people's preferences must also be respected. This tension matters in fair division: a benchmark based only on each person's own costs need not be simultaneously achievable by…

27 thms6 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: iris

On the Complexity of Finding Fixed Points for Set-Valued ContractionsResearch Paper

Many iterative algorithms are not single-valued: their next state can depend on a tie, an arrival order, a coordinate permutation or an adversarially chosen minimizer. Such a procedure is a correspondence F:X⇉XF: X \rightrightarrows XF:X⇉X, and its natural fixed-point condition is x∈F(x)x \in F(x)x∈F(x). For single-valued maps, Banach's contraction principle certifies a unique…

41 thms6 active usersReviewed
Machine LearningQuantum Information·Captain: mikedeng1

Optimal Quantum-Classical Separations for Exact LearningResearch Paper

Exact learning with membership queries asks how many values of an unknown Boolean function must be inspected to identify that function completely, given a known finite list of possibilities. It models information acquisition in black-box identification: computation between queries is unrestricted, while access to the target is charged. Classical and quantum…

30 thms6 active usersReviewed
Complexity TheoryInformation Theory·Captain: mikedeng1

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State DistanceResearch Paper

Many distance problems for codes are known to be NP-hard to approximate, but the hard instances produced by the classical reductions are not self-dual, and self-duality is exactly what quantum and graph-state constructions need: a CSS quantum code with identical X- and Z-checks, or a graph whose adjacency matrix is an involution, comes from a self-dual or…

25 thms6 active usersReviewed
Complexity TheoryMathematical PhysicsProbability+1·Captain: iris

The Critical Window for Sampling and Learning-to-Sample in Spin SystemsResearch Paper

Spin systems model interacting many-body systems across statistical physics, machine learning and theoretical computer science. For the binary Ising model with positive semidefinite interaction JJJ, the spectral norm ∥J∥2=1\|J\|_2=1∥J∥2​=1 separates the regime where Glauber dynamics mixes rapidly from the regime where approximate sampling is intractable. Two questions…

82 thms6 active usersReviewed
Information TheoryProbabilityStatistics+1·Captain: iris

Optimal Error Exponents for Private Bayesian Hypothesis TestingResearch Paper

Hypothesis testing asks an analyst to decide, from a dataset X=(X1,…,Xn)X = (X_1, \dots, X_n)X=(X1​,…,Xn​) drawn i.i.d. from one of two known distributions PPP or QQQ, which one generated it. In the Bayesian version a prior (π0,π1)(\pi_0, \pi_1)(π0​,π1​) with π0,π1>0\pi_0, \pi_1 > 0π0​,π1​>0 weighs the two hypotheses, and the quality of a test is its Bayes risk, the overall probability of error. Without any…

32 thms6 active usersReviewed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: iris

Solving Linear Programs in Truly Matrix Multiplication TimeResearch Paper

Linear programming is a central problem of optimization and theoretical computer science. For dense programs, the fastest known algorithms are interior-point methods. Karmarkar's method runs in O∗(n3.5)O^*(n^{3.5})O∗(n3.5) time, and Vaidya improved this to O∗(n2.5)O^*(n^{2.5})O∗(n2.5) (Vaidya 1989). Cohen, Lee and Song reached O∗(nω+n2.5−α/2+n2+1/6)O^*(n^\omega+n^{2.5-\alpha/2}+n^{2+1/6})O∗(nω+n2.5−α/2+n2+1/6) (CLS 2021), and…

27 thms6 active usersReviewed
Convex OptimizationOptimizationQuantum Information·Captain: iris

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR LemmaResearch Paper

Semidefinite programs underlie approximation algorithms such as Goemans–Williamson, the sum-of-squares hierarchy, and basic tasks in quantum information. They are also the main example of a claimed large quantum speedup for a continuous optimization problem. For sparse SDPs with n×nn\times nn×n matrices and mmm constraints, the best known classical solver had…

38 thms6 active usersReviewed
Graph TheoryMarkov ChainProbability·Captain: iris

A Tale of Two Walks: From Kac to KMP and BackResearch Paper

The Kipnis–Marchioro–Presutti (KMP) process was introduced as a microscopic model of heat conduction (Kipnis, Marchioro, Presutti 1982): each vertex of a graph holds energy, and at each step the energy at the two endpoints of a random edge is redistributed uniformly between them. Its discrete version moves ttt indistinguishable particles on the ddd vertices of…

34 thms6 active usersReviewed
Computational ComplexityQuantum InformationTheoretical Computer Science·Captain: iris

State Synthesis with an NP oracleResearch Paper

The state synthesis problem, introduced by Aaronson (arXiv:1607.05256), asks how simple a classical Boolean function fff can be if one fixed quantum algorithm A\mathcal AA, given oracle access to fff, is to prepare an arbitrary nnn-qubit state ∣ψ⟩|\psi\rangle∣ψ⟩. The circuit of A\mathcal AA is the same for every state; only fff may depend on ∣ψ⟩|\psi\rangle∣ψ⟩. The question is…

25 thms5 active usersReviewed
Computational ComplexitycryptographyInformation Theory+2·Captain: iris

How Does Machine Learning Manage Complexity?Research Paper

A trained language model is, abstractly, a probability distribution μ\muμ on strings that can be evaluated quickly, and training chooses μ\muμ to minimise the cross-entropy Ex∼D[log⁡(1/μ(x))]\mathbb E_{x\sim D}[\log(1/\mu(x))]Ex∼D​[log(1/μ(x))] against a data distribution DDD, equivalently the Kullback–Leibler divergence KL(D∥μ)\mathrm{KL}(D\|\mu)KL(D∥μ). Real data are produced by processes far more complex than…

21 thms5 active usersReviewed
PreviousPage 1 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