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.

1496 missions

Missions

901–925 of 1496
Open1374Completed122All1496
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Recovery Beats Storage: Improved Space for Preprocessed 3SUMResearch Paper

The 3SUM problem asks whether finite integer sets A,B,CA,B,CA,B,C contain values a,b,ca,b,ca,b,c with a+b=ca+b=ca+b=c. When many instances draw from the same large sets, preparing information once can reduce the cost of subsequent instances. Preprocessed 3SUM with unknown CCC permits preparation of AAA and BBB, while every query supplies its own subsets and its own target set. This separates…

20 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Lifting to Unary Sherali–Adams over ParitiesResearch Paper

A propositional proof system certifies that a collection of Boolean constraints has no satisfying assignment. Its resources depend on the language in which certificates are written. For Sherali–Adams, a certificate uses a polynomial identity together with nonnegative combinations of conjunctions of literals. Bounds on polynomial degree alone do not control…

27 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with DelaysResearch Paper

An online matching service must decide both whom to pair and when to stop waiting. Pairing immediately can spend too much on distance; waiting for a closer partner charges every unmatched participant. The minimum cost bipartite matching with delays problem makes this tradeoff precise when requests can only be paired with servers. Both types arrive over…

27 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCsResearch Paper

In an edge-colored graph, a rainbow cycle is a cycle on which no color occurs twice. Extremal graph theory asks how much average degree forces such a cycle. The properly colored case already connects this question to bounds for locally correctable codes. Lin's submission extends the graph theorem to nonnegative edge weights and edges bearing several colors…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Second-Best Trade Is Half Efficient in Multidimensional MarketsResearch Paper

A trading platform may know which transactions are feasible without knowing which ones create value. Buyers privately know their willingness to pay, while sellers privately know their costs. The gains from trade are the buyers' total value minus the sellers' total cost. A mechanism must elicit these numbers while giving participants a reason to report…

24 thms2 active usersReviewed
Complexity TheoryProbabilityStatistics·Captain: mikedeng1

The Polynomial-Time Low-Degree Conjecture is FalseResearch Paper

The low-degree method studies whether a statistic given by a polynomial of bounded degree can distinguish a structured random observation from an unstructured one. In statistical inference and average-case complexity, failure of such tests is often used as evidence that efficient algorithms will also fail. The polynomial-time conjecture considered here adds…

18 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Derandomizing (Fragments of) Arthur–Merlin with Range AvoidanceResearch Paper

An Arthur–Merlin protocol lets a computationally limited verifier inspect a claim with help from a prover. The verifier first sends random bits publicly; the prover then supplies a response. Perfect completeness means that every random challenge on a YES input admits an accepting response. Soundness limits how often any response can succeed on a NO input.…

20 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Traveling Salesman Problem on Graphs with Proportional Independent SetResearch Paper

A Hamiltonian cycle, or tour, visits every vertex of a finite graph exactly once and returns to its starting vertex. The traveling salesman problem asks for a tour of minimum total edge cost, or a determination that no tour exists. It matters in exact combinatorial optimization because a fast feasibility algorithm need not extend to arbitrary weighted…

21 thms2 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

A General Framework for Matching with DelaysResearch Paper

An online service that handles requests in pairs must balance two costs: connecting incompatible requests and making requests wait. A request's best partner may arrive later, but that possibility cannot justify indefinite postponement. Minimum-cost perfect matching with delays isolates this decision: every request must eventually receive exactly one…

45 thms2 active usersReviewed
AlgebraComplexity Theory·Captain: mikedeng1

An Algebraic Polynomial Evaluation Datastructure for Fields of Large CharacteristicResearch Paper

A polynomial evaluation datastructure stores a precomputed encoding of a multivariate polynomial so that the polynomial can be evaluated at any point by reading only a few cells of the encoding. Such structures were introduced for univariate polynomials in the cell-probe literature (Miltersen 1995) and were developed for multivariate polynomials as a tool…

18 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Tight weighted paging with delay via mirror descentResearch Paper

A cache can avoid repeated downloads by retaining useful pages. When requests may wait, it can also batch several requests for the same page into one download. These two choices interact: waiting may save a fetch, but holding a page while waiting occupies space that another page needs. Weighted paging with delay asks for an online rule that balances these…

19 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?Research Paper

Routing models compare what individual users prefer with the total delay experienced by all users. Exact optimization of a user's route is a strong behavioral requirement: users may accept alternatives whose delay is only slightly worse than the best available. The resulting relaxation raises a quantitative question even when demands, available routes, and…

16 thms2 active usersReviewed
🏆Completed
AlgebracryptographyInformation Theory·Captain: mikedeng1

Proximity Gaps for Gabidulin Codes and ApplicationsResearch Paper

A verifier checking a large encoded object often sees only a small portion of it. Such a check needs a relation between local consistency and distance from a valid encoding. A proximity gap provides one such relation: along an affine line of received words, sufficiently many points close to a code force a common explanation for the two words defining the…

28 thms2 active usersReviewed
CombinatoricsInformation TheoryProbability·Captain: mikedeng1

List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List DecodingResearch Paper

A code is a collection of words used to distinguish messages after transmission errors. When errors make unique recovery impossible, list decoding permits several candidate messages. Its combinatorial requirement is that a ball around any received word contain only a limited number of codewords. Researchers in coding theory study how that list size grows as…

19 thms2 active usersReviewed
Convex OptimizationOptimization·Captain: mikedeng1

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle RatesResearch Paper

A first-order oracle reveals an objective's value and one subgradient at a queried point. For a convex function, these observations support optimization without a formula for the function. The geometry of the feasible set matters: a Euclidean-Lipschitz objective on a small ℓ1 ball need not have the same query complexity as optimization on a Euclidean ball.…

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

New bounds for online coloring three-colorable graphsResearch Paper

A proper coloring assigns different colors to adjacent vertices of a graph. In the online vertex-coloring problem, vertices arrive one at a time with their edges to earlier vertices, and each color choice is immediate and irrevocable. The algorithm has to commit before learning which future vertices will connect to its current color classes. This separates…

12 thms2 active usersReviewed
Algorithmic Game TheoryComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Tarski Fixed Points in Quasi-FPT QueriesResearch Paper

Tarski's fixed point theorem says that every monotone map on a complete lattice has a fixed point. On the finite grid [n]k={1,…,n}k[n]^k=\{1,\dots,n\}^k[n]k={1,…,n}k with the coordinatewise order, finding such a fixed point captures several problems whose complexity is open: pure Nash equilibria of supermodular games, and the reductions of parity games, mean-payoff games, Condon's…

27 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Quantum interaction can superactivate cheating under parallel repetitionResearch Paper

Parallel repetition is the standard way to amplify soundness: if two non-communicating provers cannot win a game with certainty, one expects them to be even less able to win many independent copies played at once. For classical games this is Raz's parallel repetition theorem. Bhattacharyya, Mančinska and Zhao show that this intuition fails badly for quantum…

20 thms2 active usersReviewed
Machine LearningQuantum Information·Captain: mikedeng1

Quantum 1-PCA with Pauli Measurements in Nearly Linear TimeResearch Paper

Quantum PCA asks for a classical description of the leading eigenvector of an unknown mixed state ρ\rhoρ on nnn qubits, given copies of ρ\rhoρ. The leading eigenvector is the best pure-state approximation of ρ\rhoρ, and recovering it is the natural task when the state of interest is pure but the prepared state is corrupted by noise or misspecification; it is…

21 thms2 active usersReviewed
Complexity TheoryMachine Learning·Captain: mikedeng1

Polynomial-Time Mistake-Bounded Language GenerationResearch Paper

Language generation in the limit (Kleinberg and Mullainathan, 2024) asks a learner who sees a stream of words of an unknown language LLL from a known family to output, from some point on, words of LLL it has not yet seen. Unlike Gold's identification in the limit, generation is possible for every countable family. Kleinberg, Peale and Reingold (arXiv:2605.10809,…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Three Standard Deviations Suffice While One Does NotResearch Paper

A collection of measurements can depend on the same binary decisions. Each decision contributes a real coefficient to each measurement, and choosing its sign changes all measurements at once. Discrepancy theory asks how small all resulting totals can be made simultaneously. In the matrix formulation, the columns describe decisions, the rows describe…

15 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Witness Isolation with Inverse-Polylogarithmic Success Implies NP in P/polyResearch Paper

A witness is a binary string certifying that an instance has a positive answer. For a Boolean circuit, a witness is an assignment on which the circuit outputs one. Many reductions in complexity theory become useful when exactly one witness survives. Witness isolation therefore asks for a procedure that restricts a satisfiable instance while retaining…

21 thms2 active usersReviewed
Complexity TheoryProbability·Captain: mikedeng1

Random (log⁡n\log{n}logn)-CNF Formulas Are Hard for Depth-222 Frege with Modular GatesResearch Paper

A propositional contradiction can have very different proof lengths in different systems. Polynomial calculus measures the algebraic complexity of a contradiction by the largest polynomial degree needed to derive the constant one from its equations. For random formulas, the relevant question is whether many constraints make a contradiction easy to certify…

26 thms2 active usersReviewed
🏆Completed
AlgebraAnalysis·Captain: mikedeng1

Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational FunctionsResearch Paper

A real sequence is holonomic when it satisfies a linear recurrence whose coefficients are rational functions of the index. Such sequences include many combinatorial sums and the coefficient sequences of solutions of linear differential equations with polynomial coefficients. Whether a holonomic sequence is positive, or ultimately positive, is relevant to…

16 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian CertificatesResearch Paper

A proper coloring assigns a label to each vertex of a graph so that adjacent vertices have different labels. A graph is three-colorable when such an assignment exists using three labels. Knowing that three colors suffice does not supply the assignment. The approximation question asks how many colors an efficient algorithm can guarantee under that promise.…

22 thms2 active usersReviewed
PreviousPage 37 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen10026267
2DBdbenbenn55272
3SHshivm1620
4PAparclytaxel110123
5GAgaryholm900
6WCwcysai8486
7A1a142857a7518
8SCSenrui Chen6757
9BEbersubs6574
10MTmartelus trismortuus600

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