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.

1499 missions

Missions

1276–1300 of 1499
Open1321Completed178All1499
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
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
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
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
Computational ComplexityLinear algebra·Captain: mikedeng1

Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz–Petrov GeneralizationResearch Paper

A tensor decomposition expresses a multidimensional array as a sum of outer products of vectors. Its factors describe separate contributions in each coordinate direction. In applications such as latent-variable estimation and spectral data analysis, a decomposition is useful when those contributions can be distinguished from other explanations of the same…

17 thms1 active userReviewed
cryptographyGraph TheoryInformation Theory·Captain: mikedeng1

Non-Interactive Network Sum-Secure ComputationResearch Paper

Several users may need a server to compute an aggregate while protecting the aggregate from an observer of the communication network. Here the confidential object is the sum itself. The users' individual inputs are arbitrary deterministic values; there is no prescribed probability distribution on those inputs. Bai, Guang and Wang formulate this task with…

14 thms1 active userReviewed
cryptographyMarkov ChainProbability·Captain: mikedeng1

Comparison is All You Need: Settling the ttt-wise independence of AESResearch Paper

A block cipher maps fixed-length plaintext blocks to ciphertext blocks using a secret key. One way to study its statistical behavior is to fix several distinct plaintexts and ask whether their ciphertexts resemble the outputs of a uniformly random permutation. This is approximate t-wise independence: it controls every test of the joint outputs at those…

21 thms1 active userReviewed
Computational ComplexityOperations ResearchOptimization·Captain: mikedeng1

Settling the Approximability of Submodular Facility LocationResearch Paper

Submodular facility location asks how to assign clients to facilities when the cost of serving a group has diminishing marginal increments. All facilities share the same cost function. This homogeneous setting distinguishes the question from variants with a different function at each facility. It allows economies of scale while retaining the geometric…

25 thms1 active userReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A General Technique for Metrical Task Systems with Action PredictionsResearch Paper

An online movement problem reveals requests one at a time. A decision maker must serve the current request without seeing the remaining requests, and moving between possible decisions has a cost. In caching, the decision records the contents of a cache; in server problems, it records server locations. Predictions can recommend the next decision, but an…

10 thms1 active userReviewed
Algorithmic Game TheoryCombinatoricsEconomics+1·Captain: Shuze Chen

Existence of the Core in Approval-Based Committee ElectionsResearch Paper

In an approval-based committee election, each of nnn voters reports the set of candidates she approves, and a committee of kkk candidates must be chosen. Proportional representation asks that every group of voters large enough to "deserve" some seats, and united enough to agree on candidates, gets them. The strongest standard axiom of this kind is the core: no…

17 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Decentralized Dynamic Stable MatchingResearch Paper

Two-sided matching markets with stable outcomes — students and schools, workers and firms, users and servers — are classically solved by a central clearinghouse running deferred acceptance (Gale and Shapley, 1962). Many markets have no such clearinghouse: participants act on local information, and the population changes over time without announcement. A…

31 thms1 active userReviewed
CombinatoricsDiscrete GeometryProbability+1·Captain: iris

Replicable Mean Estimation via Random Lattice RoundingResearch Paper

A randomized algorithm is ρ-replicable if two runs on independent samples, sharing their random seed, return the same output with probability at least 1−ρ1-\rho1−ρ (Impagliazzo–Lei–Pitassi–Sorrell 2022). Many replicable algorithms (PAC learning, bandits, hypothesis testing) reduce to replicable mean estimation in Rd\mathbb R^dRd. Hopkins, Impagliazzo, Kane, Liu and…

23 thms1 active userReviewed
Computational ComplexityProbabilityTheoretical Computer Science·Captain: iris

The Space Complexity of Property TestingResearch Paper

Property testing asks for randomized algorithms that query a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} at a few points and decide, with probability at least 2/32/32/3, whether fff has a property P\mathcal PP or is ε\varepsilonε-far from it, meaning that at least an ε\varepsilonε fraction of its values must change to land in P\mathcal PP. The classical resource is the number…

32 thms1 active userReviewed
Computational ComplexityMachine LearningProbability+1·Captain: iris

Memory-Sample Tradeoffs for Agnostically Learning HalfspacesResearch Paper

Agnostic learning of halfspaces asks for a linear classifier whose error is within ε\varepsilonε of the best halfspace, with no assumption on how labels are generated. Statistically the problem is easy: O(d/ε2)O(d/\varepsilon^2)O(d/ε2) samples suffice in dimension ddd. Computationally it is not: the best known algorithms run in time dpoly(1/ε)d^{\mathrm{poly}(1/\varepsilon)}dpoly(1/ε) or …

34 thms1 active userReviewed
CombinatoricsComplexity Theorycryptography+1·Captain: iris

Towards Asymptotically Optimal Pseudorandom Functions: Linear-Size Circuits with Exponentially Small BiasResearch Paper

A keyed function family FK:{0,1}n→{0,1}nF_K:\{0,1\}^n\to\{0,1\}^nFK​:{0,1}n→{0,1}n is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size O(n)O(n)O(n), and it should resist attacks running in time 2Ω(n)2^{\Omega(n)}2Ω(n). Whether both are possible at once is open in general. Dinur and Ishai settle the half that…

27 thms1 active userReviewed
PreviousPage 52 of 60Next

Top contributors

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

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