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

951–975 of 1321
Open1321Completed178All1499
Information TheoryProbabilityQuantum Information+1·Captain: iris

Regev's Reduction Reaches ReconstructionResearch Paper

Sampling from the Gibbs distribution of a spin glass at low temperature is a central primitive of statistical physics and optimization. For sparse random constraint systems, the question of which temperatures are reachable in polynomial time is usually tied to the dynamical glass transition, which Mézard and Montanari identified with a reconstruction…

34 thms2 active usersReviewed
Graph TheoryProbabilityStatistics+1·Captain: iris

Planted Dense Subgraph Conjectures Are EquivalentResearch Paper

The planted clique and planted dense subgraph problems are the standard average-case hard problems behind a large family of reductions in statistics and learning theory: sparse PCA, community detection, submatrix localization, tensor PCA and robust estimation all inherit computational lower bounds from them (Brennan, Bresler, Huleihel, COLT 2018; Brennan,…

26 thms2 active usersReviewed
Computational GeometryMachine LearningNumerical Analysis+1·Captain: iris

Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product BoundsResearch Paper

Softmax attention is the basic operation of Transformers (Vaswani et al., 2017). Direct evaluation compares every query with every key, so a context of length nnn costs n2n^2n2 exponentials even when the dimension is fixed. A question for theory is whether this quadratic cost is necessary, and how attention relates to the classical batch maximum inner product prob…

30 thms2 active usersReviewed
Complexity TheoryLinear algebraMarkov Chain+1·Captain: iris

Hardness Self-Amplification in Linear Algebra and Fine-Grained CryptographyResearch Paper

Fine-grained cryptography asks for primitives secure only against adversaries of moderate polynomial running time. One natural candidate is the map f(M,x)=(M,Mx)f(M,x)=(M,Mx)f(M,x)=(M,Mx): evaluating it takes Θ(n2)\Theta(n^2)Θ(n2) field operations, while the best known way to invert it solves a linear system in nω+o(1)n^{\omega+o(1)}nω+o(1) operations, where ω\omegaω is the matrix multiplication exponent (Alm…

26 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: iris

When Does Private Data Collection Need Interaction? Online Selection under Local Differential PrivacyResearch Paper

Platforms that select contributions under limited resources increasingly see their users only through randomized reports. Federated learning systems choose participants for each round from signals of local utility, crowdsourcing assigns arriving workers to tasks of limited capacity, and large telemetry deployments run client-side randomization as the…

34 thms2 active usersReviewed
CombinatoricsOptimizationProbability+1·Captain: iris

Optimal Vertex Sampling for Constraint Satisfaction ProblemsResearch Paper

How many variables of a constraint satisfaction problem must be inspected to estimate its optimum? The natural estimator picks kkk of the nnn variables uniformly at random, solves the subproblem induced on them, and multiplies its optimum by (n/k)r(n/k)^r(n/k)r, where rrr is the arity. This estimator underlies the approximation schemes for dense instances (Arora–Karger–Karpin…

33 thms2 active usersReviewed
CombinatoricsConvex OptimizationOptimization+1·Captain: iris

Iterative Rounding for Determinant Maximization and Real Stable PolynomialsResearch Paper

In matroid-constrained determinant maximization one is given vectors v1,…,vn∈Rdv_1,\dots,v_n\in\mathbb R^dv1​,…,vn​∈Rd and a matroid M\mathcal MM on [n][n][n], and seeks a base BBB maximizing det⁡(∑i∈Bvivi⊤)\det(\sum_{i\in B}v_iv_i^\top)det(∑i∈B​vi​vi⊤​). The problem appears as D-optimal design in statistics, in determinantal point processes, in Nash social welfare, and in convex geometry. The determinant is one…

25 thms2 active usersReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: iris

Faster Power Series Composition in Fixed Positive CharacteristicResearch Paper

Truncated power series composition asks, given the coefficients of an outer polynomial f(y)=∑i<mfiyif(y)=\sum_{i<m}f_iy^if(y)=∑i<m​fi​yi and an inner polynomial g(x)=∑j<ngjxjg(x)=\sum_{j<n}g_jx^jg(x)=∑j<n​gj​xj over a commutative ring RRR, for the first nnn coefficients of f(g(x))f(g(x))f(g(x)). It is a basic operation of computer algebra: with f=F mod ynf=F\bmod y^nf=Fmodyn and g=G mod xng=G\bmod x^ng=Gmodxn for power series with G(0)=0G(0)=0G(0)=0 it computes F(G(x)) mod xnF(G(x))\bmod x^nF(G(x))modxn…

28 thms2 active usersReviewed
Information TheoryProbabilityTheoretical Computer Science·Captain: iris

Optimal Communication for Distributed Sparse Histogram AggregationResearch Paper

Histogram estimation asks how often each item of a large universe occurs in a collection of data; it underlies stream summaries, frequent-item identification and counting queries. When the data are spread over many users, a server learns the frequencies from short messages, and the question is how many bits an accurate aggregate requires. A typical regime…

45 thms2 active usersReviewed
CombinatoricsMachine LearningProbability·Captain: iris

A Sharp Dynamic Haussler LemmaResearch Paper

Haussler's packing lemma bounds the number of functions needed to approximate a class of VC dimension ddd on a fixed sample: a static cover of size (C/ε)O(d)(C/\varepsilon)^{O(d)}(C/ε)O(d), independent of the sample size (Haussler 1995). Online learning needs a dynamic version, where the instances arrive one at a time, a cover is a family of prediction rules that see only the…

41 thms2 active usersReviewed
Information TheoryProbabilityStatistics·Captain: iris

Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testingResearch Paper

A sequential test observes data one at a time and may stop and reject the null hypothesis at any moment, while keeping the probability of a false rejection below a prescribed level α\alphaα no matter how the data are monitored. Modern constructions of such tests are e-processes: nonnegative wealth processes that start at one and cannot grow in expectation…

24 thms2 active usersReviewed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: iris

Efficient Algorithms for Minrank and Index Coding for Low-Treewidth GraphsResearch Paper

The minrank of a graph was introduced by Haemers as an upper bound on the Shannon capacity. Its main motivation today is index coding: a sender broadcasts a string x∈Fqnx \in \mathbb F_q^nx∈Fqn​ to nnn receivers, receiver iii wants xix_ixi​ and already knows the coordinates indexed by its out-neighbours in a knowledge graph GGG, and the question is how short the broadcast can…

49 thms2 active usersReviewed
Algebraic TopologyCombinatoricsGraph Theory+1·Captain: iris

Improved Lower Bounds on Tree CoversResearch Paper

A tree cover approximates a finite metric by a few trees instead of one. For an nnn-point metric space (X,d)(X, d)(X,d), an (α,k)(\alpha, k)(α,k)-tree cover is a family of kkk edge-weighted trees T1,…,TkT_1, \dots, T_kT1​,…,Tk​ on the vertex set XXX such that every tree dominates the metric, dTi(x,y)≥d(x,y)d_{T_i}(x,y) \ge d(x,y)dTi​​(x,y)≥d(x,y), and every pair x,yx, yx,y is approximated within a factor α\alphaα in at least one tree.…

36 thms2 active usersReviewed
Machine LearningMathematical PhysicsQuantum Information+1·Captain: iris

The stationarity test: a framework for learning quantum many-body systems from their thermal statesResearch Paper

A quantum many-body system at thermal equilibrium is described by the Gibbs state ρH=e−βH/tr⁡e−βH\rho_H=e^{-\beta H}/\operatorname{tr}e^{-\beta H}ρH​=e−βH/tre−βH of its Hamiltonian HHH at inverse temperature β\betaβ. Hamiltonian learning asks to recover HHH from copies of ρH\rho_HρH​. It is an inverse problem in quantum physics, a primitive for certifying quantum simulators, and a quantum analogue…

31 thms2 active usersReviewed
CombinatoricsComplexity TheoryQuantum Information+1·Captain: iris

On Clifford hierarchy testing and near-extremizers of noncommutative uniformity normsResearch Paper

The Clifford hierarchy of Gottesman and Chuang [GC99] is a nested sequence of gate sets C(1)⊆C(2)⊆C(3)⊆⋯\mathcal C^{(1)}\subseteq\mathcal C^{(2)}\subseteq\mathcal C^{(3)}\subseteq\cdotsC(1)⊆C(2)⊆C(3)⊆⋯ that describes which operations can be implemented by gate teleportation with Clifford gates and magic states. Its first level is the Pauli group, its second the Clifford group, and its…

21 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Replicable Parity Learning: Cubic Sample Complexity and a Geometric CharacterizationResearch Paper

A randomized learning algorithm is replicable if two runs that share their internal random seed but receive independent samples from the same distribution return the same output with high probability. Impagliazzo, Lei, Pitassi and Sorrell introduced the notion as a guard against results that change when an experiment is repeated on fresh data (ILPS22). It…

34 thms2 active usersReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: iris

Frequency Moments Beyond Equality: Streaming Cosine Density MomentsResearch Paper

The frequency moments Fk=∑xfxkF_k=\sum_x f_x^kFk​=∑x​fxk​ of a data stream, where fxf_xfx​ counts the occurrences of item xxx, are the founding problem of streaming algorithms (Alon, Matias, Szegedy 1999). They measure how concentrated a stream is under equality: two items interact only if they are identical. Streams of embeddings, documents and feature vectors call for a softer…

35 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Local Search with Correlated RandomnessResearch Paper

Randomized local search is usually analysed with fresh, independent random bits at every step. Real executions draw their randomness from a single stream that may be biased, correlated, or partly predictable, and an algorithm cannot extract clean bits from such a stream without a seed of its own: for the semi-random sources of Santha and Vazirani no…

31 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

The Price of Anarchy of Draft AuctionsResearch Paper

The draft auction of Devanur, Morgenstern and Syrgkanis (arXiv:1311.2820) sells mmm items in rounds. In each round every bidder names one per-item price and a set of remaining items, and the highest bidder takes her set at her price. It sits between two simple formats: the single-bid auction of Devanur, Morgenstern, Syrgkanis and Weinberg (doi:10.1145/2764468.…

25 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

On the Power of Polynomial Calculus over Non-Boolean DomainsResearch Paper

Polynomial calculus (PC) is an algebraic proof system: to show that a set of polynomials has no common root, one derives the constant 111 from them by linear combinations and multiplication by variables. It is the proof-theoretic counterpart of Gröbner-basis computations and of algebraic SAT solvers, and size lower bounds for it are lower bounds on the…

56 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsMechanism Design+1·Captain: iris

The Hardness of Dominant Strategy Mechanism Design, RevisitedResearch Paper

In a combinatorial auction, mmm items are allocated among nnn bidders, each holding a private valuation of bundles, and the goal is high welfare ∑ivi(Si)\sum_i v_i(S_i)∑i​vi​(Si​). Two obstacles interact: the bidders must communicate for a good allocation to be found, and they may manipulate the protocol. A mechanism is truthful when following the prescribed strategy is an…

29 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Lossless Hardness Condensation in Deterministic Communication ComplexityResearch Paper

In two-party communication complexity, Alice holds a row x∈Xx\in Xx∈X, Bob holds a column y∈Yy\in Yy∈Y, and they must compute a Boolean entry M(x,y)M(x,y)M(x,y) by exchanging bits. The input sets can be far larger than the cost: a problem of cost ccc may have inputs of length much more than ccc. A basic structural question is whether the difficulty of a problem is already visible on a…

24 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

On the Computational Power of Geometrically Local QAC circuitsResearch Paper

Constant-depth quantum circuits with gates of bounded arity cannot compute a function that depends on all bits of a growing input: the backward light cone of the output qubit contains only constantly many inputs. Moore's class QAC⁰ removes this obstruction by allowing generalized Toffoli gates of unbounded arity, together with arbitrary one-qubit unitaries,…

47 thms2 active usersReviewed
Complexity TheoryNumerical AnalysisProbability+1·Captain: iris

Delegating Computation with Approximate Arithmetic: Interactive Proofs for WizardsResearch Paper

Interactive proofs let a computationally weak verifier check a computation carried out by an untrusted prover (Goldwasser–Micali–Rackoff 1989, Babai 1985). The protocol of Goldwasser, Kalai and Rothblum (GKR, JACM 2015) makes this efficient for both parties for arithmetic circuits over a finite field: the prover runs in time polynomial in the circuit size,…

26 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: iris

Kendall–tau Center Admits a PTASResearch Paper

Rank aggregation combines several rankings of the same candidates into one. Voting, meta-search and the combination of classifier outputs all produce such inputs. The center version of the problem asks for a ranking that is close to every input at once: it minimizes the largest disagreement with any input, not the average one. This makes it the natural…

38 thms2 active usersReviewed
PreviousPage 39 of 53Next

Top contributors

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

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