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

951–975 of 1496
Open1374Completed122All1496
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

Hardness Amplification of Approximate Nash Equilibrium with Constantly Many PlayersResearch Paper

Computing a Nash equilibrium asks for a probability distribution over each player's actions such that no player benefits from changing its own distribution. An approximate equilibrium permits a specified additive improvement. The approximation parameter matters: when payoffs lie between zero and one, allowing improvement one makes every profile acceptable.…

24 thms2 active usersReviewed
CombinatoricsComplexity TheoryOperations Research·Captain: mikedeng1

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint AssignmentResearch Paper

Local search is the oldest heuristic for the Traveling Salesman Problem (TSP): start from a tour and keep replacing it by a better neighboring tour until no neighbor is better. For the 2-opt neighborhood, studied by Croes in 1958, a move replaces two edges of the tour by two other edges. The method is used in practice, and the number of its iterations is…

29 thms2 active usersReviewed
🏆Completed
Harmonic AnalysisMachine Learning·Captain: mikedeng1

The Spectral Cost of Sharpness: Fourier Truncation, the Gibbs Bend, and the Computability of ClassificationResearch Paper

A classifier that is a finite Fourier sum cannot jump. Sharpness, meaning how quickly a classifier passes from confidently negative to confidently positive across a decision boundary, therefore has a price in bandwidth, the largest frequency it uses. Wenwei Li's manuscript The Spectral Cost of Sharpness (STOC 2027 submission #122) puts a number on that…

24 thms2 active usersReviewed
Mechanism Design·Captain: mikedeng1

On the Menu Complexity of Consumer Utility MaximizationResearch Paper

Allocating a scarce service can require a recipient to incur a cost without giving the provider revenue: waiting, paperwork and other costly participation requirements are examples. Consumer utility measures the value of an allocation after subtracting those costs. A designer maximizing it must consider both who receives a service and what recipients must…

16 thms2 active usersReviewed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

A Tight Superlinear Lower Bound on the Sketching Dimension of Weighted Spectral SparsificationResearch Paper

A spectral sparsifier of a weighted graph is a matrix that approximately preserves every quadratic form of its Laplacian. Sparsifiers are used to compute cuts and flows, solve Laplacian systems and cluster graphs. In the linear sketching model the graph is accessible only through a small number of fixed linear measurements of its edge weights. This model…

28 thms2 active usersReviewed
CombinatoricsGraph TheoryInformation Theory·Captain: mikedeng1

Optimal girth-dependent bounds for the Bethe approximation of the permanentResearch Paper

The permanent of an n×nn\times nn×n matrix, per(A)=∑σ∈Sym(n)∏iAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in\mathrm{Sym}(n)}\prod_i A_{i,\sigma(i)}per(A)=∑σ∈Sym(n)​∏i​Ai,σ(i)​, is the partition function of the weighted perfect-matching model, and computing it is #P-hard even for 0–1 matrices (Valiant 1979). Randomized approximation to any factor 1+ε1+\varepsilon1+ε is possible in polynomial time (Jerrum–Sinclair–Vigoda 2004),…

27 thms2 active usersReviewed
CombinatoricsDiscrete GeometryRandom Matrix Theory·Captain: mikedeng1

The Sharp Dimension Bound in the Johnson–Lindenstrauss LemmaResearch Paper

A collection of vectors is often used through the distances between its elements. Reducing the number of coordinates is useful only if those distances remain reliable. Euclidean dimension reduction asks how small the target dimension can be when every pairwise distance must be preserved to a specified relative accuracy. The question is relevant to metric…

5 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

Convergent Dynamics in Second Price Autobidding GamesResearch Paper

Online advertising platforms sell impressions through repeated auctions in which advertisers do not bid by hand: an autobidder scales each value by a pacing multiplier αi∈[0,1]\alpha_i\in[0,1]αi​∈[0,1] so that the advertiser's spending stays within its budget. When every advertiser paces at once, the multipliers interact, and the natural steady state is a second-price…

68 thms2 active usersReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: iris

Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion StreamsResearch Paper

Statistical analyses are often adaptive: an analyst inspects earlier results on a data set before choosing the next test. When the tests are chosen this way, the empirical answers on a fixed sample can overfit, and a result that looks significant may only reflect the sample [HU14, SU15, DFH+15b]. Adaptive data analysis turns this into a question about…

35 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

A Hitting Set Lemma for HDX & ApplicationsResearch Paper

The hitting set lemma for expander graphs bounds the probability that a random walk stays inside a fixed set of vertices: for a graph whose normalized second singular value is at most λ\lambdaλ and a set SSS of density μ\muμ, a (d−1)(d-1)(d−1)-step walk from a random vertex stays in SSS with probability at most μ(μ+λ)d−1\mu(\mu+\lambda)^{d-1}μ(μ+λ)d−1. Results of this type underlie…

29 thms2 active usersReviewed
Graph TheoryProbabilityStatistics·Captain: iris

Distinguishability Threshold for Random Geometric GraphsResearch Paper

The binomial random graph G(n,p)G(n,p)G(n,p) joins every pair of nnn vertices independently with probability ppp. Many real networks are instead built from proximity: each vertex carries a hidden position, and nearby vertices are joined. The spherical random geometric graph G(n,d,p)G(n,d,p)G(n,d,p) is the high-dimensional version of this model. In high dimension the geometry should wash…

29 thms2 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Fully Scalable MPC Algorithms for Euclidean Clustering: Constant Approximation in Constant RoundsResearch Paper

Power-zzz Facility Location is the Lagrangian relaxation of (k,z)(k,z)(k,z)-Clustering, the problem family that contains kkk-Median (z=1z=1z=1) and kkk-Means (z=2z=2z=2): instead of a hard limit of kkk centers, every opened center costs a uniform price λ>0\lambda>0λ>0. A solution of the relaxation is useful for clustering only if it is Lagrangian multiplier preserving (LMP): its connection…

27 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

A Near-Linear Element-Kernel for d-Hitting SetResearch Paper

ddd-Hitting Set is a central covering problem of parameterized complexity: many deletion problems whose obstructions have bounded size (Cluster Vertex Deletion, Feedback Vertex Set in Tournaments, Split Vertex Deletion, ddd-Path Vertex Cover) are instances of it. A kernel shrinks an instance in polynomial time to an equivalent one whose size depends on the…

38 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

Second-Best Gains from Trade in Matching MarketsResearch Paper

Two-sided markets match buyers with sellers: labor markets, ride-sharing, advertising exchanges, procurement. If every buyer's value and every seller's cost were public, a designer would choose the feasible set of trades with the largest total surplus, the first best. Values and costs are private, and the Myerson–Satterthwaite theorem (Myerson and…

60 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Quantum State Search with Classical Interactive AdviceResearch Paper

Unstructured search over 2n2^n2n items needs Θ(2n/2)\Theta(2^{n/2})Θ(2n/2) quantum queries (Grover; Bennett, Bernstein, Brassard and Vazirani), and a prover who knows the marked item removes that cost by sending its nnn-bit address. The question behind this mission is whether classical communication helps in the same way when the hidden object is a quantum state.

39 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Complete Characterization of Central String Queries in Compact SpaceResearch Paper

Text indexes such as compressed suffix trees answer queries about a string TTT of length nnn over an alphabet [0 . . σ)[0\,.\,.\,\sigma)[0..σ) while using space close to the nlog⁡σn\log\sigmanlogσ bits of the text itself. One of their standard components is the longest common prefix information of the sorted suffixes. Sadakane [Sad02] showed that the permuted LCP array PLCPT\mathrm{PLCP}_TPLCPT​ ca…

85 thms2 active usersReviewed
Machine LearningOperations ResearchOptimization+1·Captain: iris

A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum ClusteringResearch Paper

k-minsum clustering asks for a partition of a finite point set into kkk clusters minimizing the sum of all intra-cluster distances. It is a density-based clustering objective: unlike k-center, k-median or k-means, it charges every pair of points that share a cluster, so it has no notion of a cluster center. Its complement, the sum of inter-cluster distances,…

33 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Sublinear Metric Distortion for MatchingResearch Paper

One-sided matching assigns nnn agents to nnn items, one item each. In many settings the cost an agent incurs from an item is a distance (a commute, a mismatch of skills, a travel time), but a mechanism can only ask agents to rank items, not to report distances. Metric distortion measures the price of this restriction: agents and items lie in an unknown metric…

28 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Non-signaling PCPs as Algebraic Proofs, and Total Coefficients Lower Bounds for Sherali–AdamsResearch Paper

Succinct non-interactive arguments (SNARGs) for NP from standard cryptographic assumptions are a central open problem in cryptography. Devadas, Hopkins, Kalai, Kothari, Lombardi and Mathialagan (DHK+26) showed that non-signaling PCPs for NP whose completeness has short Extended Frege proofs yield SNARGs for NP from LWE. Chen and Jin (STOC 2027 submission)…

35 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Towards a Doubly Efficient IP = PSPACEResearch Paper

An interactive proof lets a verifier with limited resources check a claim "x∈Lx \in Lx∈L" by exchanging messages with a prover. The theorem IP=PSPACE\mathrm{IP} = \mathrm{PSPACE}IP=PSPACE of Lund, Fortnow, Karloff and Nisan and of Shamir (1992) shows that every time-TTT, space-SSS computation can be checked by a poly(S,n)\mathrm{poly}(S, n)poly(S,n)-time verifier. In those protocols the honest prover…

24 thms2 active usersReviewed
Operations ResearchQuantum InformationTheoretical Computer Science·Captain: iris

Cut-Rank Dynamic Programming for Fixed-Event Hardware-Constrained Pauli-Rotation SchedulingResearch Paper

Fault-tolerant quantum computers implement Clifford operations cheaply and non-Clifford operations such as the TTT gate expensively, so the temporal cost of a Clifford+TTT circuit is often measured by its number of non-Clifford rounds (Amy–Maslov–Mosca 2014; Prakash–Saha 2025). On hardware with sparse connectivity, a rotation about a multi-qubit Pauli axis must…

54 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

The DSIC Competition Complexity of Additive Buyers over Independent ItemsResearch Paper

A seller with mmm heterogeneous items faces nnn bidders. The revenue-optimal mechanism for this multi-item setting is in general randomized, hard to compute, and only Bayesian incentive compatible. Competition complexity measures how much a simple mechanism loses by asking a different question from approximation ratios: how many extra bidders must a simple…

31 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Square-root queries can helpResearch Paper

A quantum algorithm is usually modelled as a circuit: a sequence of discrete gates. A natural test of that modelling choice is whether an operation that is easy to apply can also be applied "halfway". Question 4 on Aaronson's list of annoying questions in quantum computing [Aar06] asks: if a unitary UUU can be applied in polynomial time, can some square root…

30 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Between CPA and CCA: Security Hierarchies for Restricted DecryptionResearch Paper

Deployed systems rarely hand an attacker a full decryption oracle, yet they rarely hand it nothing. A server may reveal whether a ciphertext decrypted correctly, whether a padding check passed, whether a decrypted record equals a candidate value, or the contents of a few fields of the record. Attacks that exploit such responses, from padding and format…

42 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Counter-Free Self-Adjusting Skip Lists: Concentration BoundsResearch Paper

A dictionary stores a set of ordered keys and answers searches. When some keys are requested far more often than others, a structure that serves frequent keys cheaply can beat the log⁡n\log nlogn cost per search of a balanced structure. The standard yardstick is the entropy benchmark of the access sequence: a structure is statically optimal if its total cost is…

63 thms2 active usersReviewed
PreviousPage 39 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