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

201–225 of 1321
Open1321Completed178All1499
Harmonic AnalysisInformation TheoryProbability+1·Captain: iris

A Nonadaptive Sparse Fourier Transform in Every DimensionResearch Paper

A sparse Fourier transform recovers the few large Fourier coefficients of a signal from far fewer samples than the signal's length, and in time polynomial in the number of coefficients rather than in the length. It is used whenever a spectrum is dominated by a small number of frequencies and reading the whole signal is expensive. The standard accuracy…

24 thms4 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: iris

Nearly Optimal Submodular Sparsification, with and without Cardinality ConstraintsResearch Paper

Many objects in combinatorial optimization are sums F=∑i=1mfiF = \sum_{i=1}^m f_iF=∑i=1m​fi​ of submodular set functions on a common ground set [n][n][n]: cut functions of directed hypergraphs, where each fif_ifi​ is one hyperedge or one server's subgraph, and aggregate welfare functions F(S)=∑ifi(S)F(S) = \sum_i f_i(S)F(S)=∑i​fi​(S) of mmm agents with submodular valuations over nnn resources. When m≫n2m \gg n^2m≫n2, storing…

28 thms4 active usersReviewed
Quantum Error CorrectionQuantum InformationTheoretical Computer Science·Captain: iris

Quantum Pseudorandom Error-Correcting CodesResearch Paper

A pseudorandom error-correcting code (PRC) is a keyed code whose codewords look uniformly random to anyone without the key, yet decode correctly after noise. Christ and Gunn introduced classical PRCs to watermark the outputs of generative models: a watermark must be invisible to an observer and must survive edits (CG24). Hsieh and Yamada ask for the quantum…

40 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Finite-Memory Search: Rational Compilation and Arithmetic Lower BoundsResearch Paper

A searcher repeatedly examines two locations, AAA and BBB, until it finds a stationary target. A search at the correct location fails with a known probability; a search at the wrong location always fails, and before success the searcher observes nothing but failure. The unrestricted problem is classical: greedy index rules go back to Blackwell and to Matula (Mat…

28 thms4 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

Gaussian Partitioning for Reliable Learning of Multi-Index ModelsResearch Paper

Many learning algorithms for Boolean functions on Rd\mathbb R^dRd rest on properties of the standard Gaussian: low-degree polynomial approximation, moment bounds, Hermite analysis. In several settings the examples a learner sees are not Gaussian even when the original input distribution is. Boosting reweights the examples during its run; a learner given only…

47 thms4 active usersReviewed
Graph TheoryMathematical LogicTheoretical Computer Science·Captain: iris

Model Checking for Metric Extensions of Monadic Second-Order LogicResearch Paper

Courcelle's theorem is the standard tool for showing that a graph problem is tractable on tree-like graphs: every property expressible in counting monadic second-order logic can be decided in time f(∣φ∣+tw(G))NO(1)f(|\varphi|+\mathrm{tw}(G))N^{O(1)}f(∣φ∣+tw(G))NO(1) (Courcelle 1992; Arnborg, Lagergren, Seese 1991). Optimization and counting versions followed (Courcelle, Mosbah 1993), as did…

49 thms4 active usersReviewed
CombinatoricsGraph TheoryQuantum Error Correction+1·Captain: iris

Linear-time erasure recovery for quantum expander codesResearch Paper

An erasure is a fault whose location is known: a qubit that has leaked out of its computational subspace, a lost photon, or a heralded atom loss is flagged, and the decoder receives the set L\mathcal LL of flagged qubits together with the syndrome of the unknown error E⊆LE\subseteq\mathcal LE⊆L. Several hardware platforms (neutral atoms, superconducting dual-rail…

37 thms4 active usersReviewed
Complexity TheoryProbabilityQuantum Information+1·Captain: iris

Verifiable quantum advantage based on polynomials with planted structuresResearch Paper

Random-circuit sampling experiments claim quantum advantage by producing samples that a classical computer cannot produce in reasonable time. The usual test, the linear cross-entropy benchmark (XEB), scores samples by their ideal output probabilities, and computing those probabilities is as hard as simulating the circuit. Every such experiment therefore…

46 thms4 active usersReviewed
CombinatoricsMarkov ChainProbability+1·Captain: iris

An FPRAS for Counting Common Bases of Two MatroidsResearch Paper

A matroid on a finite ground set UUU is a family of independent sets with the exchange property; its maximal members are its bases. Finding a common basis of two matroids M,NM,NM,N given by independence oracles is Edmonds' matroid intersection problem, solvable in polynomial time. Counting the common bases approximately had remained open: the special cases of…

28 thms4 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory+1·Captain: iris

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)Research Paper

Graphs excluding a fixed planar graph as a minor have bounded treewidth (Robertson–Seymour 1986), so every problem expressible in monadic second-order logic, Max Independent Set included, is polynomial on them. The analogous statement for induced minors, obtained by deleting vertices and contracting edges but never deleting edges, fails for problems such as…

40 thms4 active usersReviewed
Functional AnalysisOptimizationProbability·Captain: iris

New Lower and Upper Bounds for the Grothendieck ConstantResearch Paper

Grothendieck's inequality compares a bilinear form over signs with its relaxation over unit vectors. For a real matrix A=(aij)A=(a_{ij})A=(aij​), the value of ∑i,jaij⟨ui,vj⟩\sum_{i,j}a_{ij}\langle u_i,v_j\rangle∑i,j​aij​⟨ui​,vj​⟩ over unit vectors exceeds the value of ∑i,jaijεiδj\sum_{i,j}a_{ij}\varepsilon_i\delta_j∑i,j​aij​εi​δj​ over signs by at most a universal factor. The smallest such factor is the Grothendieck constant KGK_GKG​.…

57 thms4 active usersReviewed
Discrete GeometryProbabilityTheoretical Computer Science·Captain: iris

On the Propeller ConjectureResearch Paper

The propeller problem asks how to cut Gaussian space into pieces so that the pieces' Gaussian moments are as long as possible. It arose in the kernel clustering problem of machine learning (Song, Smola, Gretton, Borgwardt, 2007): given a positive semidefinite centered n×nn\times nn×n matrix and a k×kk\times kk×k pattern matrix, find the partition of {1,…,n}\{1,\dots,n\}{1,…,n} into kkk…

19 thms4 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

A polynomial scaling window for random k-SAT and a proof of the satisfiability conjectureResearch Paper

A random kkk-SAT formula on nnn Boolean variables is a conjunction of independent uniformly random clauses, each a disjunction of kkk literals on kkk distinct variables. As clauses are added, the formula passes from satisfiable to unsatisfiable, and the question of where and how fast this happens has driven work in probabilistic combinatorics, statistical physics…

25 thms4 active usersReviewed
CombinatoricsConvex OptimizationInformation Theory+2·Captain: iris

Optimal e(γ+o(1))ne^{(\gamma+o(1))n}e(γ+o(1))n-Approximation of the Permanent of Positive Semidefinite MatricesResearch Paper

The permanent of a matrix A∈Cn×nA\in\mathbb C^{n\times n}A∈Cn×n is per(A)=∑σ∈Sn∏i=1nAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​Ai,σ(i)​. Computing it exactly is #P-hard even on 0/1 matrices (Valiant 1979). For nonnegative entries a randomized approximation scheme exists (Jerrum, Sinclair, Vigoda 2004). For a Hermitian positive semidefinite matrix the entries may have…

37 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningProbability+1·Captain: iris

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPsResearch Paper

An episodic adversarial Markov decision process (AMDP) models a learner who repeats an HHH-step task for KKK episodes while an adversary fixes the loss function of every episode in advance. The learner sees only the losses of the state-action pairs it visits (bandit feedback), and it does not know the transition law. The standard measure of performance is the re…

82 thms4 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: iris

Supply-Sensitive Revenue Recovery under Unknown Buyer OrderResearch Paper

A seller with one copy of each of mmm items posts personalized item prices to independent buyers. Revenue benchmarks for this setting usually give every buyer full stock and bound expected allocations; the ex ante capped benchmark of Chawla, Rezvan, Teng and Tzamos (arXiv:2204.01962) and the buy-many benchmark of Chawla, Teng and Tzamos (arXiv:1902.10315) are…

29 thms4 active usersReviewed
Graph TheoryMarkov ChainProbability·Captain: iris

Sampling Colorings on G(n,d/n)G(n, d/n)G(n,d/n) via Glauber DynamicsResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic test case for Markov chain Monte Carlo and for the theory of spin systems: proper colourings are the zero-temperature antiferromagnetic Potts model. The simplest sampler is Glauber dynamics: pick a uniform vertex and recolour it uniformly among the colours not used by its neighbours. On…

67 thms4 active usersReviewed
Algorithmic Game TheoryMachine LearningOptimization·Captain: iris

Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial OpponentsResearch Paper

Two players repeatedly playing a zero-sum game with no-regret learning algorithms approach a Nash equilibrium: a social regret of RTR_TRT​ makes the averaged strategies an (RT/T)(R_T/T)(RT​/T)-approximate equilibrium (Freund–Schapire 1999). Standard algorithms have regret O(T)O(\sqrt T)O(T​), but optimistic algorithms, which predict the next gradient, reach constant regret, and hence…

53 thms4 active usersReviewed
Complexity TheoryMarkov ChainOperations Research+2·Captain: iris

Quasipolynomial-Time Planning for Decodable POMDPsResearch Paper

Partially observable Markov decision processes (POMDPs) model sequential decisions under hidden state: robot navigation with noisy sensors, inventory control with unobserved demand, medical treatment with imperfect tests. Exact planning in a finite-horizon POMDP is PSPACE-hard even with time-homogeneous dynamics and deterministic observations (Papadimitriou–…

41 thms4 active usersReviewed
Machine LearningMechanism DesignOperations Research·Captain: iris

The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-WiseResearch Paper

A seller with an unlimited supply of one product meets TTT customers in sequence. Each customer's value is drawn independently from a distribution FFF on [0,1][0,1][0,1] that the seller does not know, and the seller wants to earn, over the TTT rounds, nearly as much as the monopoly price pF∗p^*_FpF∗​ would earn if FFF were known. This dynamic pricing problem is a basic model of…

37 thms4 active usersReviewed
Algorithmic Game TheoryInformation TheoryMachine Learning+1·Captain: iris

Query-Sample Tradeoffs for Revenue MaximizationResearch Paper

A seller posting a price for a single item to a buyer with an unknown value distribution FFF wants a price whose revenue is close to optimal. Two kinds of data are available. A value sample reveals a buyer's value v∼Fv\sim Fv∼F exactly, as in historical bid data or surveys. A pricing query posts a price ppp and reveals only whether a fresh buyer buys, the bit …

36 thms4 active usersReviewed
Machine LearningOptimizationProbability·Captain: iris

Memory-efficient Finite-sum Optimization without Full Gradient RefreshesResearch Paper

Training a model by empirical risk minimization means minimizing an average f(x)=1n∑i=1nfi(x)f(x)=\frac1n\sum_{i=1}^n f_i(x)f(x)=n1​∑i=1n​fi​(x) of nnn component losses over x∈Rdx\in\mathbb R^dx∈Rd, where nnn is the number of data points and is often very large. A full gradient ∇f\nabla f∇f costs nnn component-gradient queries; a stochastic gradient costs one query but its noise prevents convergence with a…

21 thms4 active usersReviewed
CombinatoricsComplexity TheoryConvex Optimization+2·Captain: iris

A Faster Strongly Polynomial Time Algorithm for Submodular Function MinimizationResearch Paper

Submodular function minimization (SFM) asks for a set X⊆UX\subseteq UX⊆U minimizing a function h:2U→Rh:2^U\to\mathbb Rh:2U→R that satisfies h(X)+h(Y)≥h(X∩Y)+h(X∪Y)h(X)+h(Y)\ge h(X\cap Y)+h(X\cup Y)h(X)+h(Y)≥h(X∩Y)+h(X∪Y), given only a value oracle that returns h(X)h(X)h(X) on request. Graph and hypergraph cuts, coverage and entropy functions are submodular, and SFM is a subroutine of many algorithms in combinatorial…

26 thms4 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: iris

On the Relation Between Interval Regret and Dynamic RegretResearch Paper

Online convex optimization measures a learner against a benchmark chosen in hindsight. When the environment drifts, a single fixed benchmark says little, and two stronger measures have been studied. Interval regret (Daniely, Gonen and Shalev-Shwartz 2015) asks for small static regret simultaneously on every time interval. Dynamic regret (Zinkevich 2003; Zhan…

46 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

No-Regret Revenue Maximization in Sequential Market Making Under Inventory ConstraintsResearch Paper

A market maker quotes two prices for an asset: a bid, at which it buys, and an ask, at which it sells. It earns the spread when both sides trade, and it carries inventory risk when they do not balance: a maker that buys much more than it sells is exposed to the price of the asset itself, which defeats the purpose of quoting. Classical market-making models…

29 thms4 active usersReviewed
PreviousPage 9 of 53Next

Top contributors

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

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