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

1376–1400 of 1499
Open1321Completed178All1499
Linear algebraMathematical PhysicsOptimization+1·Captain: mikedeng1

Improved classical optimization of fermionic Hamiltonians beyond Gaussian statesResearch Paper

Finding the largest eigenvalue of an interacting fermionic Hamiltonian is a basic optimization problem in quantum chemistry and many-body physics. Even when the Hamiltonian is a low-degree polynomial in Majorana operators, it acts on a space of dimension 2n2^n2n, and computing its extremal eigenvalue to inverse-polynomial precision is QMA-hard. Classical…

15 thms1 active userReviewed
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
Complexity TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

A Degree–Size Relation for Resolution over PolynomialsResearch Paper

Propositional proof complexity asks how long a proof that a formula is unsatisfiable must be in a given proof system. Lower bounds for stronger systems bear on the limits of SAT solvers built on those systems, and algebraic proof systems were connected early on to bounded-depth Frege systems with modular counting (Buss et al., 1996). For ordinary…

18 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
PreviousPage 56 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin147148
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8DUducloc980
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