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.

1499 missions

Missions

51–75 of 1499
Open1321Completed178All1499
🏆Completed
CombinatoricsComplexity TheoryComputational Complexity·Captain: iris

The CNF Encoding Complexity of Boolean FunctionsResearch Paper

A CNF encoding of a boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is a CNF formula over the input variables and extra auxiliary variables such that f(x)=1f(x)=1f(x)=1 exactly when some setting of the auxiliaries satisfies the formula. Encodings of this kind are how problems are handed to SAT solvers, and the choice of encoding is often decisive for whether a problem can be…

84 thms5 active usersReviewed
🏆Completed
Formal VerificationMathematical LogicTheoretical Computer Science+1·Captain: Shuze Chen

Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper

Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…

31 thms5 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: mikedeng1

Random-Oracle Unitary Synthesis is ImpossibleResearch Paper

Unitary synthesis asks how a quantum circuit can implement a prescribed transformation when it may consult a classical function in quantum superposition. The choice of function can carry substantial information about the requested transformation. The question changes when that function must be sampled uniformly: how many queries are needed before the…

26 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
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Removing Spanning Trees Better Than Nash-WilliamsResearch Paper

A spanning tree is a set of network edges that connects every vertex and loses that property when any selected edge is removed. Transferring a spanning tree to another operator can leave the original network disconnected. The question studied here is how much connectivity must be sacrificed when the tree is chosen carefully. The paper gives a…

21 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
🏆Completed
Graph TheoryMarkov ChainProbability·Captain: mikedeng1

Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancyResearch Paper

An independent set is a collection of vertices containing no adjacent pair. Large independent sets are a central object in extremal graph theory and graph algorithms. A graph with maximum degree Δ always has an independent set of size at least n/(Δ+1), where n is its number of vertices. Restrictions on the edges inside neighborhoods can improve this scale…

27 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
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Moment Ambiguity and the Limits of Robust Stochastic OptimizationResearch Paper

An online decision maker often receives a summary of uncertain inputs before seeing their realized values. The secretary problem isolates one consequence of incomplete information: items arrive one at a time, and a rejected item cannot be recalled. The objective is to select a largest item. The question here is how much the entire sequence of exact moments…

32 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 3 of 60Next

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