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

576–600 of 1321
Open1321Completed178All1499
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
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
Quantum Error CorrectionQuantum Information·Captain: mikedeng1

Good Quantum Locally Testable Codes from Product ExpansionResearch Paper

An error-correcting code separates valid messages from corrupted words. A locally testable code adds a quantitative guarantee: a tester inspects only a bounded number of coordinates, always accepts codewords, and rejects a word with probability proportional to its distance from the code. Quantum error correction asks for compatible tests for two kinds of…

16 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Decoding Expander Walk Codes up to the Johnson Bound in Near-Linear TimeResearch Paper

A binary code C⊆F2NC\subseteq\mathbb F_2^NC⊆F2N​ is ε\varepsilonε-biased when every nonzero codeword has between (1−ε)N/2(1-\varepsilon)N/2(1−ε)N/2 and (1+ε)N/2(1+\varepsilon)N/2(1+ε)N/2 ones. Such codes are used throughout pseudorandomness and complexity theory, and the Gilbert–Varshamov bound shows that rate Ω(ε2)\Omega(\varepsilon^2)Ω(ε2) is possible, nearly matching the upper bound …

36 thms2 active usersReviewed
Complexity TheoryGraph TheoryProbability·Captain: mikedeng1

Breaking the Linear-Pass Barrier for DFS on Streaming DigraphsResearch Paper

Depth-first search explores an unvisited vertex by following an outgoing edge and completing the resulting recursive exploration before returning to the previous vertex. Its tree edges form a DFS forest, which includes isolated vertices as singleton trees. Directed DFS underlies familiar graph tasks such as cycle detection, topological sorting, and strongly…

13 thms2 active usersReviewed
Computational ComplexityOptimization·Captain: mikedeng1

Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Quantum SeparabilityResearch Paper

A real tensor is an array with several indices. Its size grows exponentially with its number of indices, but algorithms are measured against that explicit array size. A basic geometric question asks whether the array belongs to the unit ball of the nuclear norm, which measures the cost of expressing it as a sum of product arrays. Bernasconi and Malavolta…

31 thms2 active usersReviewed
Complexity TheorycryptographyProbability+1·Captain: Shuze Chen

Incrementally Verifiable Oracle Aided ComputationResearch Paper

AI systems increasingly answer questions by consulting external sources: databases, search engines, other models. An oracle-aided computation models this. A machine MMM runs as usual, but at designated steps it sends a query uuu to an oracle OOO and receives an answer O(u)O(u)O(u). Whoever wants to rely on the output of such a computation, without re-running it, would…

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

Tight Low-Diameter Decompositions and Tree Embeddings in Partially Dynamic GraphsResearch Paper

A probabilistic tree embedding approximates the shortest-path metric of a weighted graph by a random tree metric, so that an algorithm designed for trees can be run on a general graph at the cost of the approximation factor. It underlies approximation algorithms for network design, many online algorithms, and recent almost-linear-time maximum-flow…

20 thms2 active usersReviewed
OptimizationProbabilityTheoretical Computer Science·Captain: Shuze Chen

Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev InequalitiesResearch Paper

Sampling from a probability density πV(dx)∝e−V(x) dx\pi_V(dx)\propto e^{-V(x)}\,dxπV​(dx)∝e−V(x)dx on Rd\mathbb R^dRd, given only evaluations of VVV and its gradient, is a basic task in Bayesian computation, statistical physics and randomized optimization. Algorithms such as the unadjusted and Metropolis-adjusted Langevin methods and Hamiltonian Monte Carlo are analysed in exactly this model,…

21 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

New Algorithms for Dynamic Maximal Matching and Edge ColoringResearch Paper

A maximal matching of a graph GGG is a set MMM of edges, no two sharing a vertex, to which no edge of GGG can be added. In a static graph a greedy scan finds one in linear time. In the fully dynamic setting the graph on nnn vertices changes by single edge insertions and deletions, and the algorithm must keep a maximal matching after every change. Maximal matchings…

20 thms2 active usersReviewed
PreviousPage 24 of 53Next

Top contributors

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

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