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.

1376 open missions

Missions

326–350 of 1376
Open1376Completed120All1496
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Provably Distilling from Modern Language Models via Low Logit RankResearch Paper

Modern language models compute, at every position, a vector of logits and sample the next token from its softmax. Commercial interfaces often expose these logits: a user submits a prefix and receives the next-token logit vector. Distillation asks how much query access of this kind is needed to build a small model that samples almost the same distribution as…

20 thms3 active usersReviewed
Convex OptimizationGraph TheoryOptimization+1·Captain: Shuze Chen

Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially RobustResearch Paper

Correlation clustering asks for a partition of a vertex set that agrees as much as possible with pairwise "similar / dissimilar" labels. It is a standard model for deduplication and community detection, introduced by Bansal, Blum and Chawla (2004); minimizing disagreements is APX-hard, and a line of offline work has pushed the approximation ratio from 3 (Ail…

23 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

A General Approach to Polynomial-Time Truncated Learning via Low-Degree MomentsResearch Paper

Truncated statistics asks what can be learned about a distribution from samples that are only observed when they fall in a set SSS. The question goes back to Galton (1898) and Pearson and Lee (1908), and it arises whenever data are censored by a measuring device, a selection rule or a threshold. For the multivariate Gaussian with a known truncation set,…

18 thms3 active usersReviewed
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: iris

Reverse Reductions: From Faster SAT to Subexponential AlgorithmsResearch Paper

The Exponential Time Hypothesis (ETH) asserts that 3-SAT on NNN variables needs time 2Ω(N)2^{\Omega(N)}2Ω(N). A large part of parameterized complexity rests on it: for Vertex Cover and ddd-Hitting Set parameterized by the solution budget kkk, the standard lower bounds say that no algorithm runs in 2o(k)∣I∣O(1)2^{o(k)}|I|^{O(1)}2o(k)∣I∣O(1) time unless ETH fails (Cygan et al., Parameterized…

57 thms3 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: Shuze Chen

Algorithms for Min-Color Path with Bounded Color-DegreeResearch Paper

A robot that must move from sss to ttt through a field of obstacles, or a signal that must cross a sensor field, wants to cross as few obstacles as possible. Discretized, this is Min-Color Path: the obstacles become colors on the vertices of an arrangement graph and one asks for an sss–ttt path touching the fewest colors. The problem appears as Minimum Constraint…

26 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

Optimal Private Gaussian Multi-samplingResearch Paper

A private sampler receives a dataset of nnn records drawn from an unknown distribution PPP and releases new records that look like draws from PPP, while satisfying differential privacy (DP) with respect to the input dataset. Releasing samples instead of estimated parameters lets a downstream user run any procedure on the synthetic records without a further…

29 thms3 active usersReviewed
Quantum InformationRepresentation TheoryTheoretical Computer Science·Captain: iris

Optimal tomography of bosonic and fermionic Gaussian statesResearch Paper

Quantum state tomography asks for an estimate ρ^\hat\rhoρ^​ of an unknown state ρ\rhoρ from nnn independent copies ρ⊗n\rho^{\otimes n}ρ⊗n. For arbitrary states on Cd\mathbb C^dCd the number of copies needed to reach fidelity F(ρ,ρ^)2≥1−ε2F(\rho,\hat\rho)^2\ge1-\varepsilon^2F(ρ,ρ^​)2≥1−ε2 with probability 1−δ1-\delta1−δ is Θ((d2+log⁡δ−1)/ε2)\Theta((d^2+\log\delta^{-1})/\varepsilon^2)Θ((d2+logδ−1)/ε2) (O'Donnell–Wright 2016, Haah et al. 2016, Pe…

46 thms3 active usersReviewed
Mathematical PhysicsProbabilityQuantum Information·Captain: iris

Beyond light cones: State preparation complexity in quantum spin glassesResearch Paper

A central question in quantum complexity is which resources a quantum state must have to reach low energy for a hard, disordered Hamiltonian. For geometrically local models, light-cone arguments bound what shallow circuits can do: a depth-DDD circuit only correlates qubits inside a backward light cone. Dense spin glasses have no geometry, so light-cone…

25 thms3 active usersReviewed
CombinatoricsDiscrete GeometryOperations Research+1·Captain: Shuze Chen

An Almost-Linear Time Algorithm for Multidimensional Subset SumResearch Paper

Subset Sum asks whether some sub-multiset of given integers sums to a target. It is one of Karp's 21 NP-complete problems, and its pseudo-polynomial complexity is a long-standing benchmark: Bellman's dynamic program runs in O(nt)O(nt)O(nt) time, Pisinger's algorithm in O(nN)O(nN)O(nN) for items bounded by NNN, and a line of work brought the bound down to O~(n+N5/3)\tilde O(n+N^{5/3})O~(n+N5/3) (Pola…

21 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized LeaderResearch Paper

A balanced vertex separator removes a small set of vertices so that no remaining connected component contains most of the original graph. Such separators allow a graph problem to be divided into smaller instances. Their usefulness depends on both the number of removed vertices and the time spent finding them: a small separator with expensive construction…

25 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Improved Quantum Query Bounds for Boolean Matrix Product VerificationResearch Paper

A Boolean matrix product replaces scalar addition by OR and multiplication by AND. It describes whether a pair of objects has at least one intermediate witness: for example, whether two vertices are joined by a walk through a middle layer. Checking a proposed product is a natural alternative to computing the entire product. Researchers in quantum query…

33 thms3 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Quasipolynomial 3-Coloring of Diameter-2 Graphs via Domain Reduction from NogoodsResearch Paper

A proper three-coloring assigns one of three named colors to each vertex of a graph so that adjacent vertices receive different colors. A diameter-two graph has a direct edge or a common neighbor between every pair of distinct vertices. This promise makes the graph globally close together, but does not immediately supply a way to choose consistent colors.…

23 thms3 active usersReviewed
AlgebraAlgebraic GeometryComplexity Theory·Captain: mikedeng1

Approximate Polynomial Satisfiability is in the Counting HierarchyResearch Paper

An exact polynomial system asks for values making every output zero. Problems in algebraic complexity also ask whether zero can be approached by outputs of a polynomial map, even when no input gives zero exactly. Approximate polynomial satisfiability, abbreviated APS, expresses this second question using algebraic closure rather than numerical tolerances.…

26 thms3 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Optimal Robust Community DetectionResearch Paper

The stochastic block model is the standard random-graph model of community structure, studied in algorithms, statistics and statistical physics. In its sparse two-community form, every vertex carries a hidden label ±1\pm1±1, and edges are slightly more (or less) likely inside a community than across. The basic question is how well the labels can be recovered…

37 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Counterexamples to the Strong Roberson ConjectureResearch Paper

Lovász proved in 1967 that two finite graphs are isomorphic if and only if they have the same number of homomorphisms from every finite graph. Restricting the source graphs to a class F\mathcal FF gives a coarser equivalence, homomorphism indistinguishability over F\mathcal FF, and many equivalences of theoretical computer science are of this form: Dvořák…

31 thms3 active usersReviewed
Complexity TheorycryptographyProbability+1·Captain: iris

New Results in Adaptively-Secure Broadcast Encryption and Succinct Computational Secret Sharing from Standard LatticesResearch Paper

A programmable pseudorandom set sampler (PPS) is a dual-mode functional encryption scheme in which a secret key belongs to a set SSS of indices and a ciphertext belongs to one index iii. Ciphertexts can be produced in two modes: a public-key mode that needs no secret and encrypts nothing useful, and a secret-key mode that encrypts a message μ\muμ. The two modes…

93 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Structural Origins of Cubic Complexity in Pebble MotionResearch Paper

In the pebble motion problem, labelled pebbles sit on distinct vertices of a graph, and a move slides one pebble along an edge onto an empty vertex. The task is to transform an initial placement into a target placement. The 15-puzzle is the best-known instance. The problem is a basic model of reconfiguration under exclusion constraints, and it underlies…

18 thms3 active usersReviewed
CombinatoricsComputational ComplexityTheoretical Computer Science·Captain: iris

Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-CompleteResearch Paper

Vector addition systems (VAS), equivalently Petri nets, are a standard model of concurrent systems with unbounded resources: processes, tokens, counters that can be incremented and decremented but never go below zero. The central algorithmic question is reachability: can a given target configuration be reached from a given source? Its decidability (Mayr…

41 thms3 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

A PTAS for the Minimum Sum of Radii ProblemResearch Paper

In Minimum Sum of Radii (MSR) one is given a finite metric space (P,d)(P, d)(P,d) with ∣P∣=n|P| = n∣P∣=n and an integer k∈[n]k \in [n]k∈[n], and must partition PPP into at most kkk clusters so as to minimise the sum of their radii, where the radius of a cluster CCC is rad(C)=min⁡p∈Pmax⁡q∈Cd(p,q)\mathrm{rad}(C) = \min_{p \in P} \max_{q \in C} d(p, q)rad(C)=minp∈P​maxq∈C​d(p,q). Equivalently, one covers PPP by at most kkk balls and pays the sum of…

24 thms3 active usersReviewed
Computational ComplexitycryptographyDiscrete Geometry+1·Captain: iris

Superlattice methods for the shortest vector problem and discrete Gaussian samplingResearch Paper

The shortest vector problem (SVP) asks, given a basis of a lattice L⊂RnL\subset\mathbb R^nL⊂Rn, for a nonzero lattice vector of minimum length λ1(L)\lambda_1(L)λ1​(L). Lattice-based cryptography, which includes the post-quantum standards ML-KEM and ML-DSA, sets its parameters by the cost of the best SVP algorithms. Lattice sieves, run inside block reduction, are the attacks…

29 thms3 active usersReviewed
Complexity TheoryGraph TheoryProbability·Captain: Shuze Chen

Semi-Streaming Matching in a Single Pass II: Greedy is OptimalResearch Paper

A large graph can have far more edges than vertices. Keeping every edge in memory may therefore be impractical even when retaining a few records for each vertex is affordable. The semi-streaming model asks what can be computed under this limitation when edges arrive sequentially. For maximum matching, a simple greedy procedure retains an arriving edge…

22 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

Fully Dynamic Weighted Set Cover: Worst-Case Recourse and Update TimeResearch Paper

In weighted set cover, a universe of nnn elements and a family of sets with positive costs are given, and the task is a cheapest subfamily whose union covers the universe. The greedy algorithm is an O(log⁡n)O(\log n)O(logn)-approximation, and this is essentially optimal for polynomial-time algorithms. In the fully dynamic setting, elements are inserted into and deleted from…

25 thms3 active usersReviewed
Computational GeometryMachine LearningOperations Research+2·Captain: Shuze Chen

Dimension Reduction and Coresets for Min-Sum k-ClusteringResearch Paper

Min-sum kkk-clustering partitions a finite point set XXX into kkk clusters so as to minimise the total distance between points that share a cluster. Unlike kkk-median or kkk-means, it does not charge each point to a center, so it can recover clusters that are coherent but have no good representative point, such as two concentric rings. It is the complement of metric…

15 thms3 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Weighted Minimum Cuts and Near-Minimum Cut EstimationResearch Paper

A minimum cut of a graph with positive edge capacities is a cheapest way to disconnect it. Minimum cuts measure network reliability, and they are a basic subroutine in clustering, network design and the estimation of disconnection probabilities. A graph can have many minimum cuts: a cycle on nnn vertices has (n2)\binom n2(2n​) of them. The cactus representation of…

27 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

Geometrically Constrained Learning II: Agnostic Proper Learning of Lipschitz FunctionsResearch Paper

A predictor can have small average error and still change sharply between nearby inputs. A Lipschitz constraint controls this behavior at every pair of points: a 1-Lipschitz function changes by at most the Euclidean distance between its inputs. Learning a predictor that itself satisfies this constraint is called proper learning. The distinction matters when…

23 thms3 active usersReviewed
PreviousPage 14 of 56Next

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