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.

1321 open missions

Missions

1201–1225 of 1321
Open1321Completed178All1499
Complexity TheoryQuantum Information·Captain: mikedeng1

Exponential quantum-classical query separations for cyclic ForrelationResearch Paper

A quantum computation can encode information in the trace of a product of matrices. Understanding the classical cost of estimating that trace helps distinguish the resources supplied by quantum access from those supplied by ordinary oracle queries. The one-clean-qubit model, also called DQC1, studies computations with one initially pure qubit and an…

12 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Distributed Lower Bounds via Automatic Self-ReductionResearch Paper

Round elimination is the main technique for proving lower bounds on the number of communication rounds that distributed algorithms need to solve local graph problems. Its core is a lifting theorem: from a TTT-round algorithm for a problem Π\PiΠ it builds a (T−1)(T-1)(T−1)-round algorithm for a derived problem R(Π)R(\Pi)R(Π). When R(Π)R(\Pi)R(Π) is Π\PiΠ again (a fixed point), iterating…

10 thms1 active userReviewed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

A Spectral Theory of Local-to-Global LeakageResearch Paper

Additive secret sharing splits a secret into random shares whose sum is the secret. It underlies linear secret sharing in cryptography (Ben-Or, Goldwasser, Wigderson 1988; Benhamouda et al. 2018) and masking in side-channel protection of hardware. In both fields the question is how much a physical observer learns about the secret from noisy observations of…

25 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Thinning and Sprinkling: Robust Vertex Sampling and Almost HamiltonicityResearch Paper

A Hamilton cycle visits every vertex of a graph exactly once before returning to its starting vertex. Determining when a graph must contain such a cycle is a basic structural question. One necessary feature is resistance to fragmentation: deleting a small set of vertices cannot leave too many disconnected pieces. The parameter that quantifies this…

25 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Learning vs. Optimizing Players in Budgeted AuctionsResearch Paper

Online advertising platforms run enormous numbers of auctions, and most advertisers delegate bidding to an algorithm that spends a fixed budget over time. A standard choice is pacing: bid a multiple of the value and adjust that multiple according to spending. When one bidder uses such a rule, a competing bidder can observe it and exploit it. In games…

16 thms1 active userReviewed
CombinatoricsComplexity TheoryOptimization·Captain: mikedeng1

Randomized Query Lower Bounds for Submodular Function MinimizationResearch Paper

Submodular function minimization asks for a least-value subset when the only access to a set function is through queries of its values. It provides a common optimization framework for functions with diminishing marginal returns. Even after restricting attention to this structured class, the number of oracle calls needed to solve the problem remains a…

21 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

On the Complexities of Interactive Proofs of ProximityResearch Paper

A verifier checking a large object may have two limited resources: how many input positions it reads and how many bits it exchanges with an untrusted helper. Interactive proofs of proximity allow the helper to know the entire object while the verifier has only query access. The intended decision is approximate: membership must be accepted, and inputs…

10 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Polylogarithmic Collective Tree ExplorationResearch Paper

A team exploring an unknown tree must decide how to divide its work while paying for travel between branches. Collective tree exploration models this coordination problem with mobile agents, unrestricted communication, and edges revealed when an agent visits an endpoint. Fraigniaud, Gąsieniec, Kowalski and Pelc introduced the synchronous problem and an…

22 thms1 active userReviewed
Information TheoryProbabilityStatistics·Captain: mikedeng1

Optimal Conversion from Zero-Concentrated to Gaussian Differential PrivacyResearch Paper

Differential privacy is stated in several incompatible currencies. Zero-concentrated differential privacy (zCDP), introduced by Bun and Steinke (2016), bounds Rényi divergences between the output laws on neighbouring datasets; it composes additively and is used in deployed systems, including the 2020 U.S. Census TopDown algorithm. Gaussian differential…

16 thms1 active userReviewed
CombinatoricsGraph TheoryProbability+1·Captain: mikedeng1

Hamiltonicity of mildly pseudorandom regular graphsResearch Paper

An (n,d,λ)(n,d,\lambda)(n,d,λ)-graph is an nnn-vertex ddd-regular graph whose adjacency matrix has all non-trivial eigenvalues of absolute value at most λ\lambdaλ. The smaller λ\lambdaλ is compared to ddd, the more the graph resembles a random one. Whether such a graph has a Hamilton cycle, a cycle through every vertex, is a central question on pseudorandom graphs. Krivelevich and…

22 thms1 active userReviewed
Operations ResearchProbability·Captain: mikedeng1

Online Multi-Level Aggregation with Maximum DelayResearch Paper

Requests for a shared service often arrive at different times and locations. Combining them can save the cost of the resources they share, while waiting to combine them makes the oldest request wait longer. Multi-Level Aggregation with Maximum Delay studies this tradeoff when the resources form a tree and each service pays for its longest wait. The…

28 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Enumerating Complexity RevisitedResearch Paper

A program can describe an infinite set by printing its elements indefinitely. This makes description length meaningful even when no finite output string contains the whole object. Researchers in computability and algorithmic information theory ask how much shorter such a description can become when the program receives random bits. The relevant success…

10 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Associativity of Multiplication Is Hard for ResolutionResearch Paper

SAT and SMT solvers handle bit-vector arithmetic by bit-blasting: every bit becomes a Boolean variable and every multiplication a multiplier circuit, encoded as a CNF formula. Formulas that require reasoning about multiplication remain a known weak point of this approach in bounded model checking, arithmetic hardware verification and the verification of…

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

Metric Facility Location under Batched Random OrderResearch Paper

Online metric facility location was introduced by Meyerson [Mey01]: clients of a metric space arrive one at a time, each must be connected irrevocably to an open facility on arrival, opening a facility at a permitted site yyy costs f(y)f(y)f(y), and connecting a client costs its distance. The arrival order decides what can be guaranteed. Under a uniformly random…

25 thms1 active userReviewed
Computational GeometryProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Zonotope Containment via Adaptive Gaussian SamplingResearch Paper

A zonotope represents every sum of a finite collection of vectors when each vector's coefficient may vary independently between minus one and one. Such representations occur in reachability analysis and verification, where a geometric set describes a family of possible states. A basic question is whether all of those states belong to a prescribed outer…

13 thms1 active userReviewed
Computational ComplexitycryptographyQuantum Information·Captain: mikedeng1

Relativistic Zero KnowledgeResearch Paper

A zero-knowledge proof convinces a verifier that a statement is true without revealing anything else. That "nothing else" is defined by simulation: whatever a verifier sees in a real interaction with the provers, a simulator that does not know the secret must be able to produce on its own. In multi-prover interactive proofs (MIPs), introduced by Ben-Or,…

18 thms1 active userReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Almost Sharp Equivalence between Approximate Message Passing and Low-Degree PolynomialsResearch Paper

In many high-dimensional estimation problems the best accuracy reachable by any estimator is strictly better than the accuracy reached by known polynomial-time algorithms. Since worst-case complexity assumptions do not apply to random inputs, such statistical–computational gaps are studied through lower bounds against restricted classes of algorithms. Two…

22 thms1 active userReviewed
Group TheoryProbabilityQuantum Information+1·Captain: mikedeng1

Random unitary circuits with constant spectral gapResearch Paper

Random quantum circuits supply distributions of unitary transformations that can be sampled using local gates. They are used to study quantum dynamics and to replace uniformly random transformations when only finitely many statistical moments are needed. A spectral gap measures contraction toward Haar averaging in a representation of the group. A bound that…

23 thms1 active userReviewed
Computational ComplexityGraph TheoryNumber Theory·Captain: mikedeng1

Strongly explicit Ramanujan 2-lift towers via Hilbert modular formsResearch Paper

An expander graph supports walks that move through a large state space while using few random choices per step. Local access matters when a vertex has an nnn-bit name: a graph on 2n2^n2n vertices is useful to an algorithm only if its next neighbor can be computed without first constructing the entire graph. A compatible hierarchy adds another requirement. A walk…

19 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Pseudodeterminism and MA != NP^BPP in Communication ComplexityResearch Paper

Two parties may each hold a long binary string while needing only a short conversation to decide a shared question. Communication complexity measures the number of bits they exchange, allowing unlimited local computation. An additional participant, Merlin, can send a proposed witness to both parties before their conversation. Merlin–Arthur communication perm…

20 thms1 active userReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree ModelResearch Paper

A property tester examines a small part of a large object and distinguishes objects with a property from objects far from that property. For graph algorithms, this asks whether reading an entire graph is necessary even when an approximate decision would suffice. Fixed-graph isomorphism testing gives the algorithm a complete target graph in advance. Its only…

17 thms1 active userReviewed
Information TheoryProbability·Captain: mikedeng1

Online Random Sampling with Real ProbabilitiesResearch Paper

Simulations, randomized optimization and Monte Carlo integration consume long sequences of random variables X1,X2,…X_1,X_2,\dotsX1​,X2​,… whose target laws F1,F2,…F_1,F_2,\dotsF1​,F2​,… change from step to step and may depend on earlier outputs. The only true source of randomness is usually a stream of fair coin flips B1,B2,…B_1,B_2,\dotsB1​,B2​,…, and in cryptographic settings each flip is expensive (Eas…

24 thms1 active userReviewed
Information TheoryMathematical Logic·Captain: mikedeng1

The universal measure of nonstochastic objectsResearch Paper

At a seminar at Moscow State University on 26 November 1981, Kolmogorov proposed to call a finite object stochastic when it is a typical member of a simple finite set. In his definition, ω\omegaω lies in a set Ω\OmegaΩ of small description complexity, and ω\omegaω is nearly incompressible relative to Ω\OmegaΩ. He also asked how abundant nonstochastic objects are.…

28 thms1 active userReviewed
AlgebraComplexity TheoryLinear algebra·Captain: mikedeng1

Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed CyclesResearch Paper

A permutation monomial of a square matrix chooses one entry from each row and each column. The determinant adds these monomials with signs recording permutation parity. In a field of characteristic two, adding an element to itself gives zero, so minus one equals one. The determinant therefore gives the sum of all permutation monomials, but its signs no…

30 thms1 active userReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

A Full Complexity Dichotomy for Complex-Valued Boolean Holant ProblemsResearch Paper

A counting problem asks for the weighted number of global configurations satisfying local constraints; a complexity dichotomy decides, for every choice of local rules, whether the problem is computable in polynomial time or #P-hard. Boolean Holant problems are the most general Boolean framework in which such classifications are pursued: they contain…

48 thms1 active userReviewed
PreviousPage 49 of 53Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin147148
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8DUducloc990
9BOBoomShaKaLaaaKa93100
10IAI am wealthy925

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