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

1076–1100 of 1496
Open1374Completed122All1496
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
Complexity TheoryGraph TheoryLinear algebra+1·Captain: iris

Nested Effective Resistance Partitions and Eulerian SparsificationResearch Paper

Spectral sparsification replaces a dense graph by a sparse reweighted graph that preserves its Laplacian quadratic form up to a factor 1±ε1\pm\varepsilon1±ε. For undirected graphs the picture has been complete for over a decade: Spielman and Srivastava sample O(nε−2log⁡n)O(n\varepsilon^{-2}\log n)O(nε−2logn) edges by effective resistance (SS11), and Batson, Spielman and Srivastava show…

63 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
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: iris

High-dimensional expanders, the sparsest cut problem, and Steurer’s conjectureResearch Paper

The O(log⁡n)O(\sqrt{\log n})O(logn​)-approximation of Arora, Rao and Vazirani for the sparsest cut problem rests on a structural theorem about unit vectors satisfying the squared triangle inequality (ℓ22\ell_2^2ℓ22​ metrics): if such vectors are spread out, two linear-sized sets of them are Ω(1/log⁡n)\Omega(1/\sqrt{\log n})Ω(1/logn​) apart (ARV09). Barak, Raghavendra and Steurer showed that higher…

30 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
Computational GeometryMachine LearningTheoretical Computer Science·Captain: iris

Parallel Hierarchical Agglomerative Clustering in Low DimensionsResearch Paper

Hierarchical agglomerative clustering (HAC) is a greedy bottom-up clustering method available in SciPy, scikit-learn, fastcluster, R, MATLAB and other data science libraries. Its output, a dendrogram, can be cut at any level to obtain clusterings with any number of clusters, so users need not fix the number of clusters in advance. Different linkage functions…

26 thms2 active usersReviewed
Computational GeometryDiscrete GeometryOperations Research+1·Captain: iris

Constant Approximation Algorithms for Knapsack and Bin Packing for Convex PolygonsResearch Paper

Geometric knapsack asks which objects of a given family fit together in a limited region. It models cutting and nesting problems, where allowing rotations can improve material use. For axis-aligned rectangles, with or without quarter turns, constant-factor approximations have long been known. Under arbitrary rotations the problem was much less understood:…

46 thms2 active usersReviewed
Markov ChainMathematical PhysicsQuantum Information+1·Captain: iris

The complete phase diagram of detailed-balanced Gibbs samplers for the mean-field Heisenberg modelResearch Paper

Quantum algorithms for preparing Gibbs states mostly implement a Lindbladian, the generator of a Markovian open-system dynamics, whose fixed point is the Gibbs state. How long such a dynamics takes to relax is governed by the spectral gap of its generator, and rigorous gap bounds are the main open problem in the area. Known bounds cover commuting…

25 thms2 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

Quantum Advantage has Few Complexity ImplicationsResearch Paper

A proof of quantumness (PoQ) is an interactive protocol in which a classical verifier becomes convinced that its counterpart is quantum: an efficient quantum prover passes, and no efficient classical prover does. Every known construction, starting with Brakerski, Christiano, Mahadev, Vazirani and Vidick (2018), rests on a cryptographic assumption, and all…

75 thms2 active usersReviewed
PreviousPage 44 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