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.

1360 open missions

Missions

551–575 of 1360
Open1360Completed139All1499
Graph TheoryOperations ResearchProbability+1·Captain: Shuze Chen

Near-Linear Estimation of Network UnreliabilityResearch Paper

The unreliability uuu of a network is the probability that it becomes disconnected when its links fail at random. It is the basic reliability measure for communication and transport networks, and computing it exactly is #P-hard (Provan–Ball 1983). Approximation is therefore the only option. A Monte Carlo sample has relative variance Θ(1/u)\Theta(1/u)Θ(1/u), which is…

21 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Smallest Multiplicative Stretch for an α\alphaα-APASP Below O~(nω)\widetilde O \left(n^{\omega}\right)O(nω) RuntimeResearch Paper

All-pairs approximate shortest paths (APASP) asks, for a weighted undirected graph GGG on nnn vertices, for an estimate d[u,v]d[u,v]d[u,v] of every distance δ(u,v)\delta(u,v)δ(u,v) with δ(u,v)≤d[u,v]≤α δ(u,v)\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)δ(u,v)≤d[u,v]≤αδ(u,v). The factor α\alphaα is the stretch. Exact all-pairs shortest paths in weighted graphs has no known truly subcubic algorithm, so approximation is the standard…

22 thms2 active usersReviewed
Graph TheoryOperations ResearchProbability+1·Captain: Shuze Chen

First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted GraphsResearch Paper

All-pairs approximate shortest paths (APASP) asks for a matrix ddd with δ(u,v)≤d[u,v]≤α δ(u,v)+β\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)+\betaδ(u,v)≤d[u,v]≤αδ(u,v)+β for every pair of vertices. Static algorithms trade the stretch (α,β)(\alpha,\beta)(α,β) against running time; the classical additive tradeoffs are due to Dor, Halperin and Zwick for unweighted graphs and to Cohen and Zwick for weighted graphs,…

17 thms2 active usersReviewed
Computational ComplexityProbabilityTheoretical Computer Science·Captain: mikedeng1

Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPsResearch Paper

Random and semirandom constraint satisfaction problems (CSPs) are studied in two parallel lines of work. In refutation, the input is a CSP whose right-hand sides are random, and the task is to certify that no assignment satisfies much more than half of the constraints. In search, the input has a hidden planted assignment x∗x^*x∗ and the task is to recover it,…

8 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Batchwise List Decoding for Agnostic Stabilizer LearningResearch Paper

Stabilizer states are the states reachable from ∣0n⟩|0^n\rangle∣0n⟩ by Clifford circuits. They are classically simulable, they describe the code spaces of stabilizer error-correcting codes, and they are the reference set against which "magic" (non-stabilizerness) is measured. A natural learning question is therefore agnostic and proper: given copies of an…

33 thms2 active usersReviewed
CombinatoricsComputational ComplexityProbability·Captain: mikedeng1

The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All FugacitiesResearch Paper

The hard-core model assigns weights to independent sets of a graph, with a positive parameter controlling the preference for larger sets. Its partition function is a weighted count of these sets, and its probability distribution describes a random independent set. Approximate counting and sampling ask for algorithms whose cost grows polynomially with the…

6 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Harmonic Ranking for Edge-Weighted Oblivious MatchingResearch Paper

A query–commit matching problem combines discovery with allocation. A successful query can force an immediate decision, so learning which pairs are available cannot be separated from choosing a matching. This matters in the mathematical study of allocation rules that must act without seeing the complete compatibility graph. The edge-weighted oblivious model…

30 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway CutResearch Paper

Many graph-separation problems only care about how a small set of terminals can be cut apart, not about the rest of the graph. A mimicking network replaces a large graph by a small one that answers every such cut question exactly, and it is the standard way to obtain polynomial kernels (provably small equivalent instances) for parameterized cut problems…

37 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximating #BIS in exp⁡(O~(n1/3))\exp(\widetilde O(n^{1/3}))exp(O(n1/3)) TimeResearch Paper

Given a bipartite graph GGG, #BIS asks for the number Z(G)Z(G)Z(G) of its independent sets. Exact counting is #P-complete even on bipartite graphs (Provan–Ball 1983). In approximate counting, #BIS represents a whole class of problems equivalent to it under approximation-preserving reductions: Dyer, Goldberg, Greenhill and Jerrum showed it complete for the logically…

32 thms2 active usersReviewed
Mechanism Design·Captain: mikedeng1

Information Pricing with Independent State-Contingent Payoffs: Simple vs. Optimal MechanismsResearch Paper

An information seller can tell a decision maker something about an uncertain state before she chooses an action. The seller's revenue depends on the buyer's private payoffs and on what she can already do without buying information. For a buyer choosing between acting and not acting, the ability to act using her prior knowledge creates a free alternative…

42 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Depth Hierarchies for Symmetric Algebraic CircuitsResearch Paper

Lower bounds for general algebraic circuits are out of reach of current techniques: the strongest known results for constant depth are the superpolynomial lower bounds of Limaye, Srinivasan and Tavenas (LST25), and no strict hierarchy over constant depths is known for general circuits. One way to make progress is to restrict the circuits by a symmetry requir…

50 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Transparency in Team ContractsResearch Paper

A principal who delegates a project often knows more about its prospects than the people whose effort makes it succeed. Revealing that information changes agents’ incentives and therefore changes the payments needed to obtain their effort. The question is whether a principal can lose substantially by disclosing everything, even when she remains free to…

26 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Geometric Bin Packing Beyond Convexity: Approximation Schemes without AugmentationResearch Paper

Geometric bin packing asks how many identical containers are needed to place a collection of objects without overlap. For polygonal objects, a bounding rectangle can discard useful free space around a concavity or inside a hole. The geometric distinction matters when the required answer is an actual placement in unit squares. The paper studies this problem…

15 thms2 active usersReviewed
Complexity TheoryInformation TheoryMachine Learning·Captain: mikedeng1

Autoregressive Distribution Learning and Universal CompressionResearch Paper

Large language models are autoregressive: they predict the next symbol of a string given the previous ones. A good next-symbol predictor yields a good compressor by arithmetic coding, and it is folklore that "prediction is compression". Hirahara and Nanashima (STOC 2027 submission #793, October 2026) turn this into an exact complexity-theoretic equivalence.…

22 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized SpeedupsResearch Paper

A graph records pairwise conflicts: vertices are objects, and an edge says that its two endpoints cannot receive the same label. Deciding whether three labels suffice is the 3-coloring decision problem. Exact algorithms must return the correct answer on every input, including graphs without such a coloring. Their worst-case exponential running time is…

38 thms2 active usersReviewed
CombinatoricsNumber TheoryQuantum Error Correction·Captain: mikedeng1

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCsResearch Paper

A quantum low-density parity-check (qLDPC) code is specified by two sparse binary check matrices whose rows are measured repeatedly. Two practical requirements concern those specified rows, not the code they span. First, small-set soundness (also called confinement, Hong–Guo–Lucas 2025): an error of small reduced weight must violate a proportional number of…

25 thms2 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: mikedeng1

Improved Transversal Non-Clifford Gates from Cup ProductsResearch Paper

Quantum error correction stores logical information across many physical systems so that local errors can be detected and corrected. Performing useful operations on that information can introduce further errors. A transversal gate distributes the operation across physical systems with limited interaction, controlling error propagation. The target here is a…

19 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Query-optimal quantum simulation of Lindblad evolutionResearch Paper

A quantum system interacting with its environment can lose information even when its isolated dynamics would be reversible. A Lindblad equation describes a finite system whose environment acts as a memoryless reservoir. Efficient simulation of this evolution is relevant both to modeling dissipative physical systems and to algorithms using dissipative…

23 thms2 active usersReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: mikedeng1

Differentially Oblivious Priority Queues with Sublogarithmic CostResearch Paper

A priority queue stores records with priorities and supports insertion and removal of a record with smallest priority. Such queues are building blocks for graph algorithms and event processing. Ordinary implementations access memory according to the stored keys. An observer of an encrypted server can therefore learn information from addresses even when…

12 thms2 active usersReviewed
CombinatoricsMathematical PhysicsProbability+1·Captain: mikedeng1

Color coding for the Sherrington–Kirkpatrick modelResearch Paper

Mean-field spin glasses are random probability distributions on the hypercube {±1}n\{\pm1\}^n{±1}n, introduced by Sherrington and Kirkpatrick as idealized models of disordered magnets. Their normalizing constant, the partition function, is a random variable depending on Gaussian disorder. Approximating it to small relative error, with high probability over the…

5 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Explicit Subspace Evasive Sets via Subspace DesignsResearch Paper

A large collection of vectors may concentrate heavily inside a line, plane, or another small-dimensional space. Subspace evasive sets prevent that concentration: they retain many vectors while placing an upper bound on every such intersection. These sets arise in coding theory when a decoding procedure leaves candidates inside a low-dimensional space.…

21 thms2 active usersReviewed
Graph TheoryOptimizationTheoretical Computer Science·Captain: mikedeng1

Better Approximation for Sparsest Cut Oracles with Balance GuaranteesResearch Paper

A sparse cut separates a network across edges whose total capacity is small compared with the weight on either side. Such cuts identify bottlenecks. They are also used repeatedly when dividing graphs into expanding pieces and constructing representations of network congestion. In these applications, the size of a returned piece matters: repeatedly removing…

32 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean normResearch Paper

A quantum computer simulates a time-independent physical system by implementing the evolution generated by its Hamiltonian. The same operation supplies a computational primitive for eigenvalue estimation and quantum linear systems. When a matrix is given through queries to its sparse entries, the number of those queries measures how much information the…

22 thms2 active usersReviewed
Functional AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

Regularity lemma for Gaussian polynomialsResearch Paper

A fixed polynomial degree does not limit the number of variables a random polynomial can use. A quadratic polynomial can involve millions of independent Gaussian coordinates, while its distribution may resemble a function of only a few new random variables. Understanding which parts of this complexity matter is a question in Gaussian analysis and in the…

25 thms2 active usersReviewed
CombinatoricsOptimizationProbability·Captain: mikedeng1

Bootstrap, Recolor, Verify: Hierarchical Integrality Gap Instance for 0-extensionResearch Paper

Assigning network vertices to prescribed terminals is a basic form of discrete labeling. A label has a location in a metric space, and an edge pays its weight times the distance between its endpoints' labels. The optimization problem asks for a labeling of minimum total cost while keeping the terminals fixed. Researchers studying approximation algorithms…

17 thms2 active usersReviewed
PreviousPage 23 of 55Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn690113
3SHshivm1630
4PAparclytaxel150172
5MTmartelus trismortuus1050
6GAgaryholm900
7WCwcysai8486
8A1a142857a7518
9SCSenrui Chen6757
10BEbersubs6574

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