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

1176–1200 of 1496
Open1374Completed122All1496
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

The Limits of Posted Prices in Random-Order Combinatorial AuctionsResearch Paper

In a combinatorial auction a seller allocates mmm items M=[m]M=[m]M=[m] among nnn bidders, bidder iii holding a private valuation vi:2M→R+v_i:2^M\to\mathbb R_+vi​:2M→R+​, and wants an allocation (S1,…,Sn)(S_1,\dots,S_n)(S1​,…,Sn​) of pairwise disjoint bundles with large welfare ∑ivi(Si)\sum_i v_i(S_i)∑i​vi​(Si​). Truthful mechanisms that need little communication are a central topic at the boundary of economics and computing.…

26 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Sublinear Approximations for Spanning Tree CongestionResearch Paper

A spanning tree connects every vertex of a graph while retaining no cycle. Trees provide a routing structure in which every pair of vertices has exactly one simple path. This removes routing choices, but can concentrate many demands on a few tree edges. Spanning tree congestion measures that concentration when the original graph's edges are the demands.…

23 thms1 active userReviewed
Complexity TheoryGraph TheoryOptimization+1·Captain: mikedeng1

Shortest Disjoint Paths in Planar GraphsResearch Paper

This mission contains the full arbitrary-position search goal, all seventeen numbered milestones, thirteen local definition items and a published planarity reference. The theorem proofs are open Lean declarations.

32 thms1 active userReviewed
Computational GeometryDiscrete Geometry·Captain: mikedeng1

Polylogarithmic Approximation for Packing Convex PolyhedraResearch Paper

Three-dimensional packing occurs when a collection of parts must share a container and its volume determines a cost. In additive manufacturing, the orientation of a part can be chosen before its position because orientation affects surface quality, support requirements, and production time. A mathematical version therefore keeps each shape's orientation…

15 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

Efficient Quantum State Identity TestingResearch Paper

Given nnn unknown pure quantum states, the quantum state identity problem asks whether they are all the same. The Permutation Test decides this with one copy of each state under the exact promise that every pair is identical or orthogonal (Kada, Nishimura and Yamakami; Buhrman et al.). In practice states are only approximately identical or approximately…

18 thms1 active userReviewed
AlgebraComputational ComplexityLinear algebra·Captain: mikedeng1

The sum-of-squares complexity of linear-algebraic principlesResearch Paper

A real matrix of rank greater than rrr cannot be a product of an n×rn\times rn×r matrix and an r×nr\times nr×n matrix. This elementary obstruction becomes a different question when the permitted certificate is a polynomial identity of bounded degree. Researchers studying algebraic proof complexity ask how much degree a specified certificate system needs to express such…

10 thms1 active userReviewed
CombinatoricscryptographyProbability+1·Captain: Shuze Chen

Algorithms for Sparse LWE and LPN with Small SecretsResearch Paper

Learning with errors (LWE) asks to tell noisy linear equations b=As+e mod qb = As + e \bmod qb=As+emodq apart from uniformly random right-hand sides; its hardness underlies most lattice-based cryptography (Regev 2005). Sparse LWE, where every row of AAA has only kkk nonzero entries, was introduced by Jain, Lin and Saha (2024) as a source of efficient primitives, and the modulus-qqq ana…

21 thms1 active userReviewed
Computational GeometryOptimizationProbability+1·Captain: Shuze Chen

Adversarially Robust Streaming Algorithms for (k,z)(k, z)(k,z)-ClusteringResearch Paper

kkk-Median and kkk-Means are among the most studied clustering problems. Both are cases of (k,z)(k,z)(k,z)-clustering in Rd\mathbb R^dRd: given a dataset PPP, find at most kkk centers that minimise the sum of the zzz-th powers of the Euclidean distances from the points to their nearest center. In the dynamic geometric stream model of Indyk (2004), the data arrive as insertions and…

11 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Catalan Hashing: Efficient Linear Probing for Variable-Length ItemsResearch Paper

Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…

10 thms1 active userReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

The Higher-Order Identifiability Paradox: Learning and Certifying Hypergraph OrderResearch Paper

Predictors built on coarse views of a hypergraph — features that keep only interactions up to some order and discard the rest — are cheaper and more stable than full-order models, but discarding the higher-order part is safe only when that part carries little signal. Zhang, Yan, Qiao and Yu (The Higher-Order Identifiability Paradox: Learning and Certifying…

15 thms1 active userReviewed
Markov ChainMathematical PhysicsQuantum Information·Captain: iris

Rapid mixing of quantum spin chains at any finite temperatureResearch Paper

Thermal (Gibbs) states describe quantum systems in equilibrium, and preparing them on a quantum computer is a basic task for quantum simulation. A common route is a quantum Gibbs sampler: a Lindbladian whose dynamics converges to the Gibbs state σβ=e−βH/tr⁡e−βH\sigma_\beta=e^{-\beta H}/\operatorname{tr}e^{-\beta H}σβ​=e−βH/tre−βH from any initial state, the quantum analogue of a Markov…

27 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

A Numerical Refinement of an Exact Discrete Fourier Transform BoundResearch Paper

The discrete Fourier transform of length nnn maps x∈Cnx \in \mathbb C^nx∈Cn to (DFTnx)j=∑k=0n−1ζnjkxk(\mathrm{DFT}_n x)_j = \sum_{k=0}^{n-1}\zeta_n^{jk}x_k(DFTn​x)j​=∑k=0n−1​ζnjk​xk​, ζn=exp⁡(2πi/n)\zeta_n = \exp(2\pi i/n)ζn​=exp(2πi/n). The Cooley–Tukey factorization computes it with O(nlog⁡n)O(n\log n)O(nlogn) arithmetic operations, and Bluestein's chirp reduction extends that order of growth to every length (Cooley–Tukey 1965; Bluestein 1970). Later work…

15 thms1 active userReviewed
AnalysisOperations ResearchOptimization+2·Captain: Shuze Chen

Gain-Sharing Optimization in Randomized Primal–Dual Analysis: Structure and CertificationResearch Paper

Randomized primal–dual analysis is the standard way to prove competitive ratios for online matching and allocation: the algorithm's gain is split between dual variables, and a uniform expected dual-feasibility factor γ\gammaγ certifies a γ\gammaγ-competitive guarantee by weak duality (Devanur, Jain, Kleinberg 2013). The split is governed by a gain-sharing…

23 thms1 active userReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

The Sample Complexity of Multi-Class OmnipredictionResearch Paper

A predictor of class probabilities is often used by many downstream decision makers, each with its own loss. Omniprediction (Gopalan, Kalai, Reingold, Sharan, Wieder, 2022, arXiv:2109.05389) asks for one predictor whose best-response post-processing competes, for every loss in a class simultaneously, with every rule in a benchmark class. For binary labels…

20 thms1 active userReviewed
Machine LearningOptimizationProbability+2·Captain: Shuze Chen

Tensor Decomposition Beyond the Spectral ThresholdResearch Paper

Tensor decomposition asks, given all entries of an order-kkk tensor T=∑i=1mvi⊗kT=\sum_{i=1}^m v_i^{\otimes k}T=∑i=1m​vi⊗k​, to recover the rank-one components viv_ivi​ up to the symmetries of the problem. It underlies algorithms for dictionary learning, topic models and mixtures of spherical Gaussians. For general tensors it is intractable: computing the rank of a third-order tensor is…

18 thms1 active userReviewed
Graph TheoryMarkov ChainProbability+1·Captain: Shuze Chen

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local UniformityResearch Paper

Counting the proper kkk-colorings of a graph approximately, and sampling one nearly uniformly, are equivalent problems, and both are classical test cases for Markov chain Monte Carlo. The simplest sampler is the Glauber dynamics, which recolors one vertex at a time. Jerrum (Jer95) showed that it mixes in O(nlog⁡n)O(n\log n)O(nlogn) steps whenever k>2Δk>2\Deltak>2Δ, where Δ\DeltaΔ is…

24 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: Shuze Chen

One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential SearchResearch Paper

In research and development, procurement and delegated experimentation, an agent tries costly options with random outcomes one at a time, keeps the best outcome found, and decides when to stop; the principal sees only the outcome that is finally submitted and pays a wage that depends on it. Without an incentive problem this is Pandora's box problem (Weitzman…

19 thms1 active userReviewed
Graph TheoryInformation TheoryProbability+1·Captain: Shuze Chen

Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion ConstraintsResearch Paper

Connected components underlie single-linkage clustering, record linkage and many graph analyses. When a graph is too large to store and its edges arrive as insertions and deletions, one asks for a compact summary from which a spanning forest can be recovered: one tree spanning each connected component, built from edges currently present. A forest on vvv vertic…

22 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

An Information Hierarchy of Privacy Filters and OdometersResearch Paper

Differential privacy is usually analysed for a fixed sequence of releases, but in practice an analyst queries a database adaptively, choosing each request after seeing earlier answers, and the privacy cost of the next answer may itself depend on what has been released. Two kinds of procedures control the cumulative privacy loss of such an interaction: privac…

11 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: Shuze Chen

Order-selection Prophet Inequality (Almost) Goes I.I.D.Research Paper

In the prophet inequality a gambler sees independent nonnegative values V1,…,VnV_1,\dots,V_nV1​,…,Vn​ with known distributions one at a time and may accept at most one, irrevocably, when it is revealed; the benchmark is the prophet's E[max⁡iVi]\mathbb E[\max_i V_i]E[maxi​Vi​]. In an adversarial order the best ratio is 1/21/21/2 (Krengel–Sucheston 1977; Samuel-Cahn 1984). In the order-selection varian…

22 thms1 active userReviewed
cryptographyTheoretical Computer Science·Captain: Shuze Chen

Fresh Signatures without Fresh KeysResearch Paper

Digital signatures are transferable: a party for which a signature verifies can pass it on, and it verifies for every other party too. This is what lets authenticated Byzantine agreement and broadcast tolerate a third or more faulty parties, which pairwise authentication cannot do (Lamport, Shostak, Pease 1982; Dolev, Strong 1983). Transient faults break…

7 thms1 active userReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: Shuze Chen

Improved Bounds for Certifying Injective Norm of Sparse Random TensorsResearch Paper

The injective norm of a symmetric tensor is the largest value of its multilinear form on the unit sphere. For matrices it is the largest absolute eigenvalue and is computable in polynomial time; for tensors of order k≥3k\ge3k≥3 computing it, or even approximating it, is NP-hard in the worst case (Hillar–Lim 2013). For random tensors the injective norm is small…

24 thms1 active userReviewed
Convex OptimizationOptimizationQuantum Information+1·Captain: Shuze Chen

Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parametersResearch Paper

Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…

20 thms1 active userReviewed
AlgebraComputational ComplexityLinear algebra+1·Captain: Shuze Chen

Partial Homogenization and the Structure of Optimal Algebraic AlgorithmsResearch Paper

A quadratic map ϕ=(ϕ1,…,ϕK)\phi=(\phi_1,\dots,\phi_K)ϕ=(ϕ1​,…,ϕK​) is a tuple of quadratic forms in variables z=(z1,…,zN)z=(z_1,\dots,z_N)z=(z1​,…,zN​). Polynomial multiplication, matrix multiplication and multiplication in an algebra such as C\mathbb CC over R\mathbb RR are all quadratic maps. Algebraic complexity theory measures how many multiplications such a map needs, and the classical count is the…

15 thms1 active userReviewed
Computational GeometryMachine LearningOperations Research+1·Captain: Shuze Chen

The Price of Capacities for Clustering CoresetsResearch Paper

A coreset compresses a large data set into a small weighted set on which a family of clustering queries can be evaluated with relative error ε\varepsilonε. Coresets for Euclidean (k,z)(k,z)(k,z)-clustering (kkk-median for z=1z=1z=1, kkk-means for z=2z=2z=2) are a standard tool for streaming, distributed and approximation algorithms, and their optimal size has been the subject of a…

22 thms1 active userReviewed
PreviousPage 48 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