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.

1496 missions

Missions

1–25 of 1496
Open1378Completed118All1496
🏆Completed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Hardness of Counting Orderings: Taking Gadget Amplification to the LimitResearch Paper

A linear extension of a finite partially ordered set (poset) PPP is an ordering of its elements in which every element comes after all of its predecessors. Counting them, #LE(P)\#\mathrm{LE}(P)#LE(P), is a basic problem of order theory with uses in sorting under partial information, scheduling, and Bayesian inference over orderings. Brightwell and Winkler proved in 1991…

34 thms10 active usersReviewed
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
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Privacy for Free in Efficient Agnostic Halfspace LearningResearch Paper

A classifier trained on individual records can reveal information about those records through its output. Differential privacy bounds how much the output distribution changes when one labeled example is replaced. For halfspace learning, the statistical question is whether this protection requires substantially more examples than learning without privacy.…

33 thms9 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
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum circuit compilation with constant overheadResearch Paper

Quantum algorithms are usually written as circuits of arbitrary one- and two-qubit gates. A fault-tolerant machine executes only a finite instruction set, and a standard choice is G={H,T,CNOT}\mathcal G=\{H,T,\mathrm{CNOT}\}G={H,T,CNOT}. An arbitrary rotation cannot be written exactly over a finite gate set, so every compiler approximates. Ross and Selinger (RS16) approximate a…

31 thms8 active usersReviewed
🏆Completed
Complexity Theorycryptography·Captain: mikedeng1

Witness Encryption via Prime-Order Generic GroupsResearch Paper

Witness encryption lets a sender encrypt a bit against a mathematical statement without knowing whether that statement is true. A person who possesses a witness that the statement is true can decrypt. If the statement is false, its ciphertext must conceal the bit. This separates the ability to create a ciphertext from possession of a secret decryption key:…

43 thms8 active usersReviewed
🏆Completed
Functional AnalysisGraph Theory·Captain: mikedeng1

Improved Embedding of kkk-Outerplanar Metrics into ℓ1\ell_1ℓ1​Research Paper

A shortest-path metric records the least total edge length needed to travel between two vertices of a weighted graph. Representing these distances as sums of absolute coordinate differences connects graph geometry with routing and partitioning. In particular, the connection between metric embeddings and the fractional flow-cut gap makes distortion bounds…

26 thms8 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: iris

Quantum Algorithms for OPI Variants Beyond Locality and Classical DecodabilityResearch Paper

The code intersection problem asks for a codeword of a linear code C⊆FqmC\subseteq\mathbb F_q^mC⊆Fqm​ that lies in a prescribed set AAA. It is NP-hard even for q=3q=3q=3 and AAA a Cartesian product of per-coordinate sets (arXiv:2610.00502, §1). Optimal polynomial intersection (OPI), which asks for a low-degree polynomial whose values lie in prescribed sets at all evaluation…

80 thms8 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price MechanismResearch Paper

A broker stands between a seller and a buyer who hold private valuations. It posts a price to each side, and trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their valuations: they are simple, strategy-proof, and individually rational. When the same kind of trade repeats, the broker must…

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
🏆Completed
CombinatoricsComplexity TheoryOperations Research·Captain: mikedeng1

Near-Logarithmic Inapproximability of Parameterized Set CoverResearch Paper

Set Cover asks for a smallest selection from a family of subsets whose union contains every element of a specified universe. It is a basic model for selecting resources that jointly satisfy coverage requirements. Its approximation behavior depends on both the number of available sets and the number of elements requiring coverage. When the universe is small,…

42 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
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: iris

When are bosonic Gaussian states classical to learn?Research Paper

Bosonic Gaussian states describe laser light, thermal radiation, squeezed light and the modes of many continuous-variable quantum devices. They sit on the boundary between quantum and classical physics: a Gaussian state is fixed by a mean vector and a covariance matrix, exactly like a classical Gaussian random vector, yet some Gaussian states are entangled…

111 thms7 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryNumber Theory·Captain: iris

Prime cordial labeling of Knödel graphResearch Paper

Graph labelings assign integers to the vertices of a graph subject to arithmetic conditions on the edges; Gallian's dynamic survey (Electron. J. Combin., DS6) lists several thousand papers on them. A prime labeling asks for distinct labels 1,…,∣V∣1,\dots,|V|1,…,∣V∣ with coprime labels on every edge. Its relaxation, the prime cordial labeling of Sundaram, Ponraj and…

88 thms6 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
🏆Completed
Mathematical PhysicsProbabilityQuantum Information·Captain: mikedeng1

Fast mixing of the SYK model at high temperaturesResearch Paper

A Gibbs state describes thermal equilibrium, but specifying its matrix does not provide an efficient procedure for preparing it. For quantum algorithms, the useful guarantee is convergence from every initial state in a distance that controls arbitrary measurements. Agreement of a few local observables is insufficient for this purpose. The Sachdev–Ye–Kitaev…

33 thms6 active usersReviewed
PreviousPage 1 of 60Next

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