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.

1321 open missions

Missions

26–50 of 1321
Open1321Completed178All1499
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
cryptographyQuantum InformationTheoretical Computer Science·Captain: iris

The Entire Quantum Computer on a Classical LeashResearch Paper

A classical computer that wants to use a quantum computer it does not own faces two problems: the server may cheat, and the server sees the computation. Kalai, Khurana and Raizes (arXiv:2610.31775) show that both problems can be solved with classical messages alone, for every real quantum circuit, in the strong sense of simulation-secure two-party…

16 thms5 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Exact Sum-of-Radii Clustering under Any Constant StabilityResearch Paper

A coverage system can assign demand points to facilities with different service radii. The minimum sum-of-radii objective measures the sum of those radii rather than the largest radius or the total distance to facilities. Its optimization problem fixes the number of clusters, so making one cluster cheaper can compensate for making another more expensive.…

173 thms5 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Tight Post-Quantum Parallel Repetition for Private-Coin ArgumentsResearch Paper

Parallel repetition is the basic way to reduce the soundness error of a proof system without adding rounds: run kkk independent copies and accept if enough of them accept. The analysis is subtle, because the verifier's copies are independent but a cheating prover may correlate its answers across all of them. For computationally sound protocols the reduction…

27 thms5 active usersReviewed
CombinatoricsComplexity TheoryComputational Complexity+1·Captain: Shuze Chen

Near-Cubic Gate and Near-Quartic Wire Lower Bounds for SYM ◦THR CircuitsResearch Paper

Depth-two threshold circuits are the first case of the open problem of proving strong lower bounds against constant-depth threshold circuits, which model neural networks with linear threshold units. Superpolynomial lower bounds are open even at depth two. Williams' algorithmic method (Wil13, Wil14) turns a fast algorithm that analyzes a circuit class into a…

26 thms5 active usersReviewed
Algorithmic Game TheoryMachine LearningProbability·Captain: Shuze Chen

Minimax Realized Full Swap Regret on the Euclidean DiskResearch Paper

In online linear optimization a learner repeatedly picks a point of a convex set and then pays a linear loss chosen by an adversary. External regret compares the learner with the best single fixed point in hindsight. Swap regret is stronger: every action value the learner actually played may be replaced, in hindsight, by its own substitute. Low swap regret…

24 thms5 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

The 3-Uniform Hyperclique Hypothesis is FalseResearch Paper

A 3-uniform hypergraph records relations involving three vertices at a time. Its vertices may be any labels in a finite set, and each hyperedge consists of three distinct vertices. A four-hyperclique consists of four vertices for which every three-vertex subset is a hyperedge. Detecting this pattern has been used as a benchmark for fine-grained complexity:…

14 thms5 active usersReviewed
AlgebraComputational ComplexityNumber Theory·Captain: mikedeng1

Finding Integer Roots of Polynomials in Nearly Optimal TimeResearch Paper

An integer polynomial is specified by a finite list of signed integers. Finding its integer roots is a basic exact computation in computer algebra and a special case of solving Diophantine equations. The relevant resource is the number of operations on individual bits: an algorithm that performs few algebraic operations can still be expensive if those…

22 thms5 active usersReviewed
Quantum Information·Captain: mikedeng1

Parallel Repetition for Entangled Games via Conditional Relative EntropyResearch Paper

Parallel repetition asks how quickly a game's success probability decreases when a referee requires several independent instances to be won together. In a two-player proof system, this is a way to reduce the chance of accepting a false assertion while retaining two players and one round of communication. The question becomes different when the players share…

29 thms5 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Tight Lower Bounds for Differentially Private Continual CountingResearch Paper

A running count reports how many ones have appeared in a binary stream after each arrival. Releasing these counts privately is a basic instance of repeated statistical reporting: a single input bit contributes to many answers, so privacy must protect the complete vector of releases. Continual counting also serves as a privacy primitive in learning…

19 thms5 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

No size-preserving amplification with quantum adviceResearch Paper

Error reduction asks how much additional computation is needed to make a randomized or quantum algorithm more reliable. With auxiliary quantum information, its size is a separate resource. Quantum advice is a state that may depend on the input length but must support every input of that length. Keeping the number of advice qubits fixed asks whether an…

25 thms5 active usersReviewed
Information TheoryMachine LearningQuantum Information·Captain: iris

Universal Inductive Inference of Quantum StatesResearch Paper

Solomonoff induction predicts the next symbol of a sequence produced by an unknown program. Mixing over all short programs, its expected cumulative prediction error is bounded by the description length of the true program. Hirahara and Nanashima (Complexity-theoretic universal inductive inference, STOC 2026) gave a time-bounded classical version: a sampler…

29 thms5 active usersReviewed
Complexity TheoryComputational GeometryMachine Learning+1·Captain: Shuze Chen

Exact Euclidean k-Means: Faster in the Plane, Hard Beyond ItResearch Paper

Exact Euclidean k-means asks for the least possible sum of squared distances from data points to freely located centers. Two parameters shape the problem: the number of centers, k, and the ambient dimension, d. An algorithm whose exponent depends on their product can be polynomial for every fixed pair and still become impractical as either parameter grows.…

26 thms5 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 thms5 active usersReviewed
CombinatoricsConvex Optimization·Captain: mikedeng1

A deterministic (1+ε)n(1+\varepsilon)^n(1+ε)n approximation for the permanent of a nonnegative matrixResearch Paper

The permanent measures the total weight of ways to pair every row of a square matrix with a distinct column. For a zero-one matrix it counts perfect matchings in a bipartite graph. For general nonnegative entries it retains their weights. Counting problems use this quantity to distinguish the existence of a configuration from the total contribution of all…

31 thms5 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 thms5 active usersReviewed
Computational ComplexityMarkov ChainProbability·Captain: mikedeng1

How Hard Is It to Compute Cover Time?Research Paper

A cover time measures how long a random walk takes to visit every vertex of a graph. Its expectation distinguishes graphs that are explored quickly from graphs where some vertices remain unseen for much longer. Exact computation records information beyond a coarse estimate of exploration speed. The specified-start comparison problem asks whether the…

26 thms5 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Kawamura's pinwheel density conjecture holds for smallest period at most five and fails from sixResearch Paper

A pinwheel instance asks whether a single machine, doing one task per day, can visit each task often enough that task iii occurs in every window of aia_iai​ consecutive days. The problem models periodic servicing such as the perpetual maintenance of machines (arXiv:2202.01567), and its central question is how much of the machine's capacity can be promised in…

959 thms5 active usersReviewed
Complexity TheoryConvex OptimizationProbability·Captain: mikedeng1

A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle ModelResearch Paper

A membership oracle answers whether a specified point belongs to an unknown set. It supplies one Boolean answer per query, even when the point has arbitrary real coordinates. In convex optimization this is a basic way to describe a feasible region without giving its inequalities. The question is how many such answers an algorithm needs before it can…

24 thms5 active usersReviewed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: mikedeng1

The Exact Communication Threshold for Parallel RepetitionResearch Paper

A two-player game gives Alice and Bob related questions and asks them to produce a valid pair of answers. Each player initially sees only their own question. Such games model the separated verifiers and answer constraints used in complexity theory. Repeating a game independently is useful when simultaneous success becomes unlikely. The question addressed…

22 thms5 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Sublinear Copies Suffice for Fidelity Estimation with Pauli MeasurementsResearch Paper

A quantum experiment prepares a state, but its intended mathematical description does not certify what the apparatus actually produced. Reconstructing the entire state can require substantially more data than estimating one specified property. Fidelity estimation asks how closely an unknown preparation matches a known pure target. This mission also includes…

25 thms5 active usersReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Exponential Quantum Advantage in Testing Fourier DimensionalityResearch Paper

A central question in quantum query complexity is how large a gap can separate quantum and classical query counts for a natural property that is classically testable independently of the input length. Simon's problem and Forrelation give exponential gaps, but neither is such a property. Chen (2026) proposes Fourier dimension testing as a candidate: a…

24 thms5 active usersReviewed
Machine LearningQuantum Information·Captain: iris

Efficient Agnostic Learning of Tensor Network StatesResearch Paper

Quantum state tomography asks for a classical description of an unknown quantum state from measurements on independent copies of it. For general states on nnn subsystems the number of copies grows exponentially in nnn (O'Donnell–Wright 2016; Haah et al. 2017), so efficient reconstruction must exploit structure. Tensor network states — matrix product states…

90 thms5 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Square-root queries can helpResearch Paper

A quantum algorithm is usually modelled as a circuit: a sequence of discrete gates. A natural test of that modelling choice is whether an operation that is easy to apply can also be applied "halfway". Question 4 on Aaronson's list of annoying questions in quantum computing [Aar06] asks: if a unitary UUU can be applied in polynomial time, can some square root…

33 thms5 active usersReviewed
Computational ComplexityMachine LearningQuantum Information·Captain: iris

Fast Quantum Algorithms for Learning Linear Threshold FunctionsResearch Paper

A linear threshold function (LTF), or halfspace, labels each point of Rn\mathbb R^nRn by the side of a hyperplane on which it lies. LTFs are the classifiers of the perceptron and of linear support vector machines, and learning them is one of the oldest problems in computational learning theory.

72 thms5 active usersReviewed
PreviousPage 2 of 53Next

Top contributors

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

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