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

1226–1250 of 1496
Open1374Completed122All1496
Mathematical PhysicsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Hopfield Model with ppp-spin Interactions: Shattering, Disorder Chaos and Sampling HardnessResearch Paper

The Hopfield model is the standard model of an associative memory: MMM random patterns η1,…,ηM∈Rn\eta^1,\dots,\eta^M\in\mathbb R^nη1,…,ηM∈Rn are stored in the couplings of a spin system on {−1,1}n\{-1,1\}^n{−1,1}n by Hebb's rule, and the low-energy configurations are meant to retrieve them. Its ppp-spin (dense) version couples ppp spins at a time; it stores about np−1n^{p-1}np−1 patterns instead of about …

21 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Space and Time Cut Sparsification in Turnstile StreamsResearch Paper

A cut sparsifier of a weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) on nnn vertices is a reweighted subgraph HHH that approximates the weight of every cut of GGG within a factor 1±ε1\pm\varepsilon1±ε. Benczúr and Karger showed that every graph has one with O(nlog⁡n/ε2)O(n\log n/\varepsilon^2)O(nlogn/ε2) edges, and sparsifiers have since become a basic tool for minimum cut, maximum flow, Laplacian solvers and…

22 thms1 active userReviewed
CombinatoricsGraph TheoryMathematical Logic+1·Captain: Shuze Chen

Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler–Leman and Hypertree WidthResearch Paper

The Weisfeiler–Leman (WL) family of colour-refinement algorithms is the standard heuristic for graph isomorphism and the yardstick for the expressive power of graph neural networks. Its distinguishing power has an exact algebraic description: by Lovász's theorem two graphs are isomorphic iff every graph has the same number of homomorphisms into both, and…

22 thms1 active userReviewed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

Random-Walk Cuckoo Hashing is Efficient up to the Critical Load ThresholdResearch Paper

Cuckoo hashing stores keys in a table so that every key sits in one of a few cells determined by its hashes, which makes lookups take constant worst-case time. With ddd hashes per key, the table can be filled almost completely: Fountoulakis and Panagiotou (FP12) identified the exact load threshold 1−εd∗1-\varepsilon^*_d1−εd∗​ up to which all keys can be placed with high…

20 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Instance-Optimality of Single-Pair Personalized PageRankResearch Paper

Random walks with restart are a basic tool of network analysis. The personalized PageRank (PPR) π(s,t)\pi(s,t)π(s,t) of a target ttt with respect to a source sss measures how close ttt is to sss in a directed graph. It was introduced for personalized web search by Brin and Page, and it is now used in recommender systems, node embeddings, local clustering and graph neural…

21 thms1 active userReviewed
Machine Learning·Captain: Shuze Chen

The Sample Complexity of Multicalibration with an ERM OracleResearch Paper

A risk score is calibrated if, among the people who receive score 0.30.30.3, about 30%30\%30% have the outcome. Calibration is a statement about the whole population and says nothing about subgroups, which may be over- and under-predicted in opposite directions. Multicalibration (Hébert-Johnson et al., ICML 2018) asks for calibration simultaneously on every subgroup…

23 thms1 active userReviewed
CombinatoricsMachine LearningStatistics+1·Captain: Shuze Chen

PAC Learning with Multiple Correct AnswersResearch Paper

In many prediction tasks an input has more than one acceptable answer: a sentence has several valid translations, a scheduling instance several optimal schedules, an image several correct tags. Training data, however, often shows only one correct answer per input: a demonstration. Hanneke, Mansouri, Pour, Shaeiri and Wang (arXiv:2611.05133) ask exactly when…

23 thms1 active userReviewed
Machine LearningOperations ResearchProbability+1·Captain: Shuze Chen

Tight Bounds for k-Median++ and Improved Bounds for k-Means++Research Paper

The k-means++ seeding rule of Arthur and Vassilvitskii (AV07) picks cluster centers one at a time: the first uniformly from the input, each later one with probability proportional to its current cost. It is the default initialization of k-means in scikit-learn, Apache Spark and Google BigQuery ML, and it is a building block of local-search, streaming and…

13 thms1 active userReviewed
Harmonic AnalysisMachine LearningTheoretical Computer Science·Captain: Shuze Chen

Learning Fourier-Sparse Signals and Multiband SignalsResearch Paper

Many uses of the continuous Fourier transform observe a signal only on a bounded time window. A basic model is the kkk-Fourier-sparse signal x(t)=∑j=1kαje2πifjtx(t)=\sum_{j=1}^k\alpha_je^{2\pi i f_jt}x(t)=∑j=1k​αj​e2πifj​t with complex amplitudes and arbitrary real frequencies in a bandlimit [−F,F][-F,F][−F,F], observed through point samples of y=x+ηy=x+\etay=x+η on [−1,1][-1,1][−1,1] with adversarial noise η\etaη. When the…

24 thms1 active userReviewed
Algorithmic Game TheoryEconomicsLinear Optimization+1·Captain: Shuze Chen

Fair and Efficient Balanced Allocations for Additive ValuationsResearch Paper

Dividing indivisible items among agents with additive valuations is the core model of fair division, with applications from inheritance and divorce settlements to course allocation and shift scheduling. The standard fairness relaxation is envy-freeness up to one item (EF1) and the standard efficiency notion is Pareto optimality (PO), strengthened to fraction…

18 thms1 active userReviewed
Complexity TheoryMathematical LogicTheoretical Computer Science·Captain: Shuze Chen

The Metacomplexity Structure of Search ProblemsResearch Paper

Metacomplexity studies the complexity of computational tasks that are themselves about computation: compressing strings, estimating circuit complexity, or refuting a claimed algorithm by finding an input on which it fails. Refutation tasks appear in learning theory, in hardness magnification, in derandomization and in bounded arithmetic. A refutation task…

21 thms1 active userReviewed
AlgebraNumerical AnalysisProbability+1·Captain: Shuze Chen

Approximate Syzygies of Smoothed Polynomials and ApplicationsResearch Paper

Many algorithms for tensor decomposition, polynomial system solving and learning mixtures reduce to linear algebra on Macaulay matrices: given polynomials b1,…,bmb_1,\dots,b_mb1​,…,bm​, the matrix of the map (h1,…,hm)↦∑ibihi(h_1,\dots,h_m)\mapsto\sum_i b_ih_i(h1​,…,hm​)↦∑i​bi​hi​ at a fixed output degree. Whether such an algorithm is robust to noise depends on how far this map is from losing rank, beyond the…

12 thms1 active userReviewed
Algorithmic Game TheoryCombinatoricsOptimization+1·Captain: mikedeng1

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item ReductionResearch Paper

In an online allocation problem, buyers arrive one at a time and each must be served irrevocably on arrival; the benchmark is the prophet, who sees all valuations in advance and allocates optimally. When the valuations are random with known distributions, guarantees of this kind are prophet inequalities. A much weaker information model gives the algorithm…

39 thms1 active userReviewed
cryptography·Captain: mikedeng1

Optimal Early-Stopping Broadcast via Exponential Information GatheringResearch Paper

A Byzantine broadcast protocol lets a designated sender distribute an input despite parties that can lie, omit messages or send different reports to different recipients. Honest parties must eventually output a common value, and that value must equal the sender’s input when the sender is honest. These requirements give distributed protocols a common value…

30 thms1 active userReviewed
Graph TheoryProbability·Captain: mikedeng1

From Oblivious to Adaptive Adversaries: Black-Box Reductions for Monotone Dynamic Problems with Applications to Cuts, Distances, and ClusteringResearch Paper

A randomized dynamic graph algorithm receives updates and maintains an answer after each one. An oblivious adversary commits to its update sequence independently of the algorithm's randomness. An adaptive adversary can choose the next update after inspecting earlier published answers. A guarantee for every fixed sequence does not automatically cover…

6 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Identifying Minimax Payoffs from Bounded InterventionsResearch Paper

A service choosing a randomized action to minimize its largest group loss solves a finite minimax problem. A user who can change row priorities and action prices can observe a sequence of such decisions without seeing the underlying losses. The identification question is whether those observations determine the payoff table. It matters for interpreting what…

28 thms1 active userReviewed
Computational ComplexityMachine Learning·Captain: mikedeng1

Depth Lower Bounds for ReLU Networks with Binary InputsResearch Paper

A ReLU network repeatedly forms affine combinations of available values and applies the function ReLU⁡(t)=max⁡(0,t)\operatorname{ReLU}(t)=\max(0,t)ReLU(t)=max(0,t). Its depth measures the number of computational layers, while its width measures the largest number of computed units in one layer. Researchers studying neural-network expressiveness ask how much width is needed when depth is…

10 thms1 active userReviewed
Discrete GeometryProbability·Captain: mikedeng1

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansionResearch Paper

Non-expansive maps of a metric space into the real line with small average distortion are a standard rounding device for graph partitioning. A relaxation (a linear or semidefinite program) produces a metric on the vertices; a 1-Lipschitz map to the line that preserves the average distance up to a factor DDD is then thresholded into a cut, and DDD becomes the…

9 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Constant-Time Range Counting for Pattern-Avoiding Permutations and Entry Access to Twin-Ordered MatricesResearch Paper

Given a permutation τ\tauτ of [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, a dominance query (x,y)(x,y)(x,y) asks how many of the first xxx values of τ\tauτ are at most yyy. Together with rectangle queries (four dominance counts by inclusion–exclusion), it is the basic primitive of two-dimensional orthogonal range counting in rank space, and it underlies succinct text indexes and compressed matrix…

21 thms1 active userReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert–Varshamov BoundResearch Paper

A stored or transmitted bit string can lose symbols, gain symbols, or change their order. Such synchronization errors disrupt the alignment between the original and received strings. A decoder therefore has to identify the original message while also resolving where its symbols moved. The paper studies a fixed number of errors as the block length grows,…

23 thms1 active userReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Exponential Quantum Advantage in Number-on-Forehead CommunicationResearch Paper

A communication problem distributes an input among several participants and asks how many bits they must exchange to compute an answer. In the number-on-forehead model, each participant sees every input block except their own. With three participants, these views overlap substantially: a fact hidden from one participant is visible to the other two. Lower…

24 thms1 active userReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Work-Efficient Parallel Rounding: Product ObjectivesResearch Paper

Randomized rounding often certifies a collection of requirements by assigning a nonnegative penalty to each failure and bounding their total expectation. When the coordinates are independent, exponential penalties for linear sums factor into products of functions of individual coordinates. Preserving the sum of these product expectations therefore provides…

9 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

An Efficient 1/4-Competitive Prophet Inequality for Subadditive Combinatorial AllocationsResearch Paper

A seller with several distinct items must often decide whom to serve before knowing the demand of later buyers. Waiting for every valuation would permit a welfare maximizing allocation in hindsight, but an online allocation must commit items as buyers arrive. This creates a quantitative question: how much welfare can a causal algorithm preserve when it…

22 thms1 active userReviewed
Formal VerificationGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Büchi Determinization with Optimal States and Square Root Index ImprovementResearch Paper

Automata on infinite words describe behavior that continues indefinitely. In formal verification, a system execution is such a word, and an acceptance condition expresses a property of its long-term behavior. Converting a nondeterministic automaton to a deterministic one can make subsequent operations possible, but the conversion has two costs: the number…

28 thms1 active userReviewed
Computational ComplexityHarmonic AnalysisProbability·Captain: mikedeng1

Testing Fourier Sparsity Near OptimallyResearch Paper

A Boolean function f:F2n→{−1,+1}f:\mathbb F_2^n\to\{-1,+1\}f:F2n​→{−1,+1} is sss-Fourier-sparse when at most sss of its Fourier coefficients are nonzero. Sparse functions include parities and kkk-juntas (which have at most 2k2^k2k nonzero coefficients), so sparsity is one of the basic "concise representation" classes of learning theory and property testing. A tester for this class reads fff at a…

16 thms1 active userReviewed
PreviousPage 50 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