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

726–750 of 1496
Open1374Completed122All1496
Complexity TheoryLogicTheoretical Computer Science·Captain: Shuze Chen

Reconfiguring Resolution RefutationsResearch Paper

A resolution refutation certifies that a CNF formula is unsatisfiable by deriving the empty clause from its clauses with the resolution rule. Resolution is the proof system behind conflict-driven SAT solvers, and its proofs are routinely post-processed: they are compressed by local rewrites, used to compute Craig interpolants for model checking, and…

18 thms2 active usersReviewed
AlgebraCombinatoricscryptography+2·Captain: Shuze Chen

Mutual Correlated Agreement and List-Decoding: Improvements and SeparationsResearch Paper

Interactive oracle proofs (IOPs) for proximity to Reed–Solomon and other linear codes, the engine of hash-based succinct arguments such as FRI, STIR and WHIR, repeatedly fold several words into one random linear combination and test only the combination. Soundness needs a guarantee in the other direction: if the combined word is close to the code, the input…

17 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Greedy BST is O(log log n)-competitiveResearch Paper

A binary search tree (BST) on the keys 1,…,n1,\dots,n1,…,n answers a sequence of searches. A balanced tree costs O(log⁡n)O(\log n)O(logn) per search, but an adaptive tree that reshapes itself can do much better on structured sequences: repeated requests, sequential scans, requests clustered in time or in key order. The dynamic optimality problem asks whether a single online BST…

15 thms2 active usersReviewed
Markov ChainProbabilityRandom Matrix Theory+2·Captain: Shuze Chen

High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear RegressionResearch Paper

The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: a Gibbs measure on {±1}d\{\pm1\}^d{±1}d whose interactions are a random Gaussian matrix. Sampling from it is a benchmark problem for Markov chain Monte Carlo. At high temperature (inverse temperature β\betaβ below an absolute constant) Glauber dynamics is known to mix rapidly, while at low temperature…

16 thms2 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Online Correlated Exponential ClocksResearch Paper

In Display Ads an ad platform must assign each arriving impression, immediately and irrevocably, to at most one advertiser. Advertiser iii values impression jjj at wij≥0w_{ij}\ge0wij​≥0 and keeps only its best impression (free disposal). The objective is ∑imax⁡j∈Siwij\sum_i\max_{j\in S_i}w_{ij}∑i​maxj∈Si​​wij​, compared with the offline optimum OPT\mathrm{OPT}OPT, the weight of a maximum-weight matching.…

25 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: Shuze Chen

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering ProblemsResearch Paper

Correlation clustering asks for a partition of the vertices of a graph whose edges are labelled "similar" or "dissimilar", agreeing with as many labels as possible. In its maximization form, MaxAgree, one maximizes the total weight of positive edges inside clusters plus negative edges between clusters. The problem was introduced by Bansal, Blum and Chawla (M…

26 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Data-Dependent Probability Estimation via Sample AmplificationResearch Paper

A statistician observes nnn independent draws S=(X1,…,Xn)S=(X_1,\dots,X_n)S=(X1​,…,Xn​) from an unknown distribution DDD on a finite domain [d]={1,…,d}[d]=\{1,\dots,d\}[d]={1,…,d}, and is then asked about an event, or more generally a [0,1][0,1][0,1]-valued query, chosen by looking at the same sample. Such data-dependent questions arise whenever a dataset is explored before it is analysed: adaptive data analysis,…

22 thms2 active usersReviewed
CombinatoricsGraph TheoryOptimal Transport+1·Captain: Shuze Chen

Graph Similarity Meets Optimal TransportResearch Paper

A common way to measure how different two graphs are is to align their vertex sets and count how much the adjacency structure disagrees under the alignment. With different matrix norms this gives graph edit distance, a standard tool in pattern recognition and graph matching (Gao et al. 2010); local edit distance, the largest number of edits needed at a…

21 thms2 active usersReviewed
Computational GeometryTheoretical Computer Science·Captain: Shuze Chen

Constant Approximation of Fréchet Distance in Near-Linear TimeResearch Paper

The Fréchet distance is a standard measure of similarity between curves. It is used for trajectory clustering, map construction and other tasks in spatio-temporal data mining (Alt 2009, cited by the paper as [Alt09]). Computing it exactly takes roughly quadratic time. Alt and Godau compute the continuous distance in O(nmlog⁡(nm))O(nm\log(nm))O(nmlog(nm)) time (1995), and Eiter and…

13 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: Shuze Chen

Ranking Beats 1-1/e on General GraphsResearch Paper

A matching in a graph is a set of edges no two of which share an endpoint. Greedy matching algorithms are the default in settings where a maximum matching is too expensive to compute or where decisions must be made in a fixed order without revision: online matching, the stochastic query-commit model of kidney exchange and online dating, and streaming. The…

19 thms2 active usersReviewed
Computational ComplexityMachine LearningProbability+2·Captain: Shuze Chen

Average-case reductions for k-XOR and Tensor PCAResearch Paper

Planted noisy kkk-XOR and Tensor PCA are two canonical average-case problems. Both have a hidden sign vector, both have a wide range of parameters where the hidden vector is determined by the data but no polynomial-time algorithm is known to find it, and both are used as hardness assumptions: kkk-XOR for learning halfspaces, DNFs and tensor completion and in…

18 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Nearly Tight Low-Stretch Ramsey Spanning TreesResearch Paper

Embeddings of metric spaces into trees and ultrametrics are a standard tool for approximation algorithms, distance oracles and compact routing: a problem on a general metric is solved on a tree and the answer is mapped back, at the price of the distortion. The metric Ramsey theorem (Bartal, Linial, Mendel, Naor 2005; Mendel, Naor, FOCS 2006) says that every …

18 thms2 active usersReviewed
CombinatoricsComplexity TheoryGroup Theory+2·Captain: Shuze Chen

Group Isomorphism: Depth-2122\frac{1}{2}221​ Circuits and Lower BoundsResearch Paper

Group Isomorphism (GpI) asks whether two finite groups, each given by its full multiplication table (its Cayley table), are isomorphic. With n=∣G∣n=|G|n=∣G∣, Miller's generator-enumeration algorithm decides it in time nlog⁡2n+O(1)n^{\log_2 n+O(1)}nlog2​n+O(1), because every group of order nnn is generated by at most log⁡2n\log_2 nlog2​n elements. Whether GpI is in polynomial time is open, and so is the…

17 thms2 active usersReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: Shuze Chen

Sensitivity and Locality Lower Bounds via Low-Soundness Label CoverResearch Paper

An algorithm is sensitive when a small edit to its input can force a large change in its output. Low sensitivity matters for dynamic and streaming computation, where outputs should change little between consecutive inputs, for stability and privacy, and for distributed computing, where a sensitivity lower bound turns into a locality lower bound. Varma and…

19 thms2 active usersReviewed
Graph TheoryProbabilityStatistics+1·Captain: Shuze Chen

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation TestingResearch Paper

Graph matching asks for the correspondence between the nodes of two structurally similar graphs. It is a quadratic assignment problem, NP-hard in the worst case, with applications such as the de-anonymization of social networks. The average-case version on random graphs is a standard testbed for the gap between what is information-theoretically possible and…

25 thms2 active usersReviewed
CombinatoricsComputational ComplexityLinear algebra+1·Captain: Shuze Chen

More on Correlation Bounds for PolynomialsResearch Paper

How well can low-degree polynomials over F2\mathbb F_2F2​ predict an explicit Boolean function? Small correlation with all degree-ddd polynomials is the input to the polynomial method for circuit lower bounds (Razborov, Smolensky) and a prerequisite for progress on questions in multiparty communication, matrix rigidity and pseudorandomness (see Viola's survey [5], …

24 thms2 active usersReviewed
AlgebraAlgebraic GeometryComputational Complexity+1·Captain: Shuze Chen

Quasilinear Encoding at the Quadratic Alphabet Scale via Short Cartier BasesResearch Paper

A linear code over a finite field FQ\mathbb F_QFQ​ encodes KKK message symbols as NNN codeword symbols; its minimum distance ddd guarantees recovery from ttt errors and eee erasures whenever 2t+e<d2t+e<d2t+e<d. The Singleton bound gives d≤N−K+1d\le N-K+1d≤N−K+1. For a target gap 0<ε<10<\varepsilon<10<ε<1 one asks for codes with

19 thms2 active usersReviewed
CombinatoricsComputational ComplexityProbability+1·Captain: Shuze Chen

Tight Bounds for Conservative Pointer JumpingResearch Paper

In the number-on-the-forehead (NOF) model of communication of Chandra, Furst and Lipton (CFL83), an input is split into kkk parts and each of kkk players sees every part except the one on its own forehead. Lower bounds in this model are hard to prove because the players' views overlap so much, and they would be valuable: by Yao (Yao90), Håstad and Goldmann (HG91…

19 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Recognizing Label-Connected GraphsResearch Paper

In the classical gossiping problem every participant holds one piece of information, and whenever two participants call each other they exchange everything they know. With all pairs allowed to call, 2n−42n - 42n−4 calls are necessary and sufficient for n≥4n \ge 4n≥4 participants (Baker–Shostak 1972; Hajnal–Milner–Szemerédi 1972). When the available calls are prescribed…

19 thms2 active usersReviewed
CombinatoricsOptimizationTheoretical Computer Science·Captain: Shuze Chen

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation SchemesResearch Paper

Weighted edit distance and other string alignment problems are computed by combining boundary-to-boundary distance matrices of planar alignment graphs. These matrices are Monge: Mij+Mi+1,j+1≤Mi,j+1+Mi+1,jM_{ij}+M_{i+1,j+1}\le M_{i,j+1}+M_{i+1,j}Mij​+Mi+1,j+1​≤Mi,j+1​+Mi+1,j​. For unweighted alignment, Tiskin showed that the matrices have a compact structure: O(n)O(n)O(n) space and O(nlog⁡n)O(n\log n)O(nlogn)-time min-plus products. That…

15 thms2 active usersReviewed
AnalysisMachine LearningProbability+1·Captain: Shuze Chen

Error accumulation in reverse diffusion with an imperfect score: beyond path-space analysesResearch Paper

Diffusion models generate samples from a data distribution ppp on Rd\mathbb R^dRd by running a stochastic differential equation backwards in time. The drift of the backward equation involves the score ∇log⁡pt\nabla\log p_t∇logpt​ of the noised data distribution, which is not known and is replaced by a neural-network estimate s^\hat ss^ trained by a squared loss. The standard…

18 thms2 active usersReviewed
Machine LearningMarkov ChainProbability+2·Captain: Shuze Chen

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber DynamicsResearch Paper

In tensor PCA (the spiked tensor model of Richard and Montanari, 2014) one observes an order-kkk tensor that is a rank-one signal buried in Gaussian noise and must recover the hidden direction. The model is a standard testbed for the gap between what is statistically possible and what efficient algorithms achieve. Weak recovery is information-theoretically…

21 thms2 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory+1·Captain: Shuze Chen

Constrained Directed Separation: Algorithms and ClassificationsResearch Paper

Directed Multicut asks to delete at most kkk nonterminal vertices of a digraph so that no directed path remains from the first to the second terminal of any demand. Olkowski and Ramanujan study what happens when the deleted vertices must also satisfy a structural condition: the subdigraph they induce must belong to a fixed hereditary class H\mathcal HH.…

27 thms2 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory+1·Captain: Shuze Chen

Once-Paid Subsequences and the Cost of Min-Plus ApproximationResearch Paper

Many sequence problems are solved by a prefix recurrence that uses only minimum and addition, and such a recurrence, once its structure is fixed before the costs are known, is a min-plus circuit. Lower bounds on min-plus circuits therefore say which recurrences cannot exist, independently of how clever the choice of states is (Jukna–Seiwert 2020).

18 thms2 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order AlgorithmsResearch Paper

Language generation in the limit asks whether a generator can eventually produce only new members of an unknown language after observing positive examples. This is a mathematical model of generation from examples; it imposes no computational resource bound. Eventual validity alone allows outputs to occupy a sparse part of the target. On the positive…

18 thms2 active usersReviewed
PreviousPage 30 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