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.

1355 open missions

Missions

901–925 of 1355
Open1355Completed144All1499
Complexity TheoryGraph TheoryLinear algebra+1·Captain: iris

Maximum-Completion Forests via Sharp Spectral QuantizationResearch Paper

Determinant maximization asks, for a positive semidefinite matrix MMM and a budget kkk, for the kkk indices SSS maximizing det⁡MS\det M_SdetMS​. For a Gram matrix this is the squared volume spanned by the chosen vectors; in a fixed-size determinantal model it is the most likely subset. For general positive semidefinite matrices the best known deterministic polynomial-time…

96 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Efficient Error Amplification for Sorting and Orthogonal VectorsResearch Paper

Derandomizing a circuit classically has two steps: reduce the error below 2−N2^{-N}2−N on NNN-bit inputs, then fix one good random string non-uniformly. The generic way to reduce the error is to run independent copies and combine their answers, and reaching error 2−k2^{-k}2−k costs a factor kkk in size. For a problem whose circuits are already close to its conjectured…

19 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Parallel Edge Ranking of TreesResearch Paper

An edge ranking of a tree assigns positive integer ranks to its edges so that the path between any two distinct edges of equal rank contains an edge of higher rank. The edge ranking number er(T)\mathrm{er}(T)er(T) is the least possible maximum rank. This number gives the minimum worst-case number of edge queries needed to locate a target element in a tree, the…

27 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

A Near-Optimal Generalized Sorting AlgorithmResearch Paper

Ordinary comparison sorting assumes that any two elements can be compared. In many settings only some comparisons are possible or affordable: in the nuts and bolts problem a nut can only be compared with a bolt, and in pairwise preference or ranking problems only certain pairs are ever presented together. Generalized sorting, introduced by Huang, Kannan and…

51 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: iris

Exact Euclidean TSP with Few Interior Points: A Square-Root ExponentResearch Paper

The Euclidean traveling salesman problem asks for a shortest closed tour through nnn given points of the plane, with costs the true Euclidean distances. It is NP-hard (Papadimitriou, 1977), and the subset dynamic program of Bellman and of Held and Karp (1962) solves it in time exponential in nnn. De Berg, Bodlaender, Kisfaludi-Bak and Kolay (SICOMP 2023) showed…

31 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFsResearch Paper

A polynomial threshold function (PTF) of degree two labels a point x∈Rdx\in\mathbb R^dx∈Rd by the sign of a quadratic polynomial; an intersection of kkk of them, f(x)=1{q1(x)≥0,…,qk(x)≥0}f(x)=1\{q_1(x)\ge0,\dots,q_k(x)\ge0\}f(x)=1{q1​(x)≥0,…,qk​(x)≥0}, describes regions bounded by kkk quadrics: ellipsoids, slabs, cones and their intersections. Learning such concepts from examples drawn from the standard Gaussian is a…

29 thms2 active usersReviewed
Markov ChainQuantum Information·Captain: iris

A mixing time method for estimating the sample complexity of quantum state discriminationResearch Paper

Quantum state discrimination asks for a measurement that identifies which of nnn known states was prepared. Its sample complexity kmin⁡(ϵ)k_{\min}(\epsilon)kmin​(ϵ) is the least number of i.i.d. copies that reaches success probability 1−ϵ1-\epsilon1−ϵ. The quantity bounds the cost of tasks in quantum algorithms and quantum learning theory, among them hidden subgroup and hidden…

38 thms2 active usersReviewed
Complexity TheoryLinear algebraQuantum Information+1·Captain: iris

The Role of Diagonal Lines in Quantum Low-Degree TestingResearch Paper

A low-degree test checks that answers to local questions come from a single global polynomial. Low-degree tests go back to the multilinearity and low-individual-degree tests of Babai, Fortnow and Lund (1991) and became central to the PCP theorem. Against provers who share entanglement the situation changes, because answers to different questions come from…

27 thms2 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Tight Bounds for Sublinear Metric Steiner TreeResearch Paper

The metric Steiner tree problem asks for a cheapest tree connecting a prescribed set of terminals in a metric space, possibly through additional points. It is one of Karp's original NP-complete problems, with a best known polynomial-time ratio of ln⁡4+ε≈1.39\ln 4+\varepsilon\approx1.39ln4+ε≈1.39 (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).

31 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignTheoretical Computer Science·Captain: iris

Truthful-in-Expectation Mechanism with Constant Maximin-Share GuaranteeResearch Paper

Dividing indivisible goods among agents with private additive valuations is a basic problem of algorithmic game theory: the agents' reports are the only input, so a rule that rewards misreporting cannot be fair with respect to the true values. A randomized mechanism is truthful in expectation (TIE) if no agent can raise her expected true value by…

43 thms2 active usersReviewed
Algebraic GeometryComplexity TheoryInformation Theory·Captain: iris

On Proximity Gaps for One-Point Algebraic Geometric CodesResearch Paper

Succinct proof systems of the FRI, STIR and WHIR family test whether a committed word lies close to a code. To test many words at once, they combine them with a random challenge: words u0,…,uℓu_0,\dots,u_\ellu0​,…,uℓ​ are replaced by the single word r(z)=∑j=0ℓujzjr(z)=\sum_{j=0}^{\ell}u_jz^jr(z)=∑j=0ℓ​uj​zj for a random zzz. Correlated agreement (CA) is the property that makes this batching sound. If…

36 thms2 active usersReviewed
Computational GeometryGraph TheoryTheoretical Computer Science·Captain: iris

Tight Bounds for (1+ϵ)(1+\epsilon)(1+ϵ)-Approximation for Minimum Spanning Trees in Doubling MetricsResearch Paper

A minimum spanning tree (MST) of a finite metric space (X,d)(X,d)(X,d) is a spanning tree of the complete graph on XXX of least total edge length. Computing it exactly from a distance oracle takes Θ(n2)\Theta(n^2)Θ(n2) distance queries even in metrics of constant doubling dimension (Andoni et al., 2014), so the question is how fast a (1+ϵ)(1+\epsilon)(1+ϵ)-approximate MST, a spanning tree…

54 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization+1·Captain: iris

Polylog Pairwise Poise: Approximating Multicommodity MulticastResearch Paper

In the synchronous telephone model, each vertex of a graph can exchange any number of messages with at most one neighbor per round. Multicommodity multicast asks, given source–sink pairs (s1,t1),…,(sk,tk)(s_1, t_1), \dots, (s_k, t_k)(s1​,t1​),…,(sk​,tk​), to deliver each source's message to its sink within the minimum number of rounds. It generalizes the single-source problems known as…

51 thms2 active usersReviewed
Complexity TheoryDynamic ProgrammingOperations Research+1·Captain: iris

Multi-Selection Pandora's Box with Nonobligatory Inspection: A PTAS and a Structural SeparationResearch Paper

Pandora's box is a basic model of costly search. Weitzman (1979) showed that a simple index policy is optimal when a box must be opened before its prize can be selected. In many settings a searcher may select an option without inspecting it: a firm may hire a candidate on their record alone. This gives Pandora's box with nonobligatory inspection (PNOI). The…

107 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Lower Bounds for the Weisfeiler-Leman Algorithm via Implicit Parity SystemsResearch Paper

The kkk-dimensional Weisfeiler–Leman algorithm (kkk-WL) is the central combinatorial heuristic for graph isomorphism. It refines a coloring of kkk-tuples of vertices round by round, and two graphs are told apart when their color statistics differ. The number of rounds is a natural measure in several fields: it equals the quantifier depth in the logic Ck+1C^{k+1}Ck+1 with…

38 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree AlgorithmsResearch Paper

An induced matching (or strong matching) of a graph is a set of pairwise vertex-disjoint edges whose endpoints span no other edges. Induced matchings appear in strong edge colouring (each colour class of a strong edge colouring is an induced matching), in the Ruzsa–Szemerédi problem, and in the analysis of graph algorithms and interference-free scheduling.…

23 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

Linear Regression with Self-Selection Bias in Polynomial TimeResearch Paper

In many data sets the recorded response is not the outcome of one fixed model but the largest of several. Workers choose among occupations and only the earnings from the chosen one are observed (Roy, 1951); auction data may reveal only the transaction price, not the winning bidder or the losing bids (Athey–Haile, 2002); the model of Fair and Jaffee (1972)…

32 thms2 active usersReviewed
Algebraic TopologyAlgorithmic Game TheoryCombinatorics+1·Captain: iris

Balanced Fair Division and Generalized Kneser GraphsResearch Paper

Many allocation problems divide indivisible goods between groups rather than individuals: households sharing what they receive, teams, or departments. Every member of a group gets the same bundle, but each member judges it with her own preferences, so a bundle that one member finds fair another may envy. Exact envy-freeness is impossible already for a…

32 thms2 active usersReviewed
Graph TheoryHarmonic AnalysisProbability+1·Captain: iris

Sharp detection thresholds for random geometric graphs with polynomial average degreesResearch Paper

A random geometric graph (RGG) hides a latent geometry: each vertex carries a random point, and edges join nearby points. In high dimension the geometry washes out, and a basic question in probability, statistics and theoretical computer science is the dimension at which the graph becomes statistically indistinguishable from an Erdős–Rényi graph with the…

34 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SATResearch Paper

A strong backdoor of a CNF formula φ\varphiφ into a tractable class is a set XXX of variables such that every assignment to XXX turns φ\varphiφ into a formula of that class. Once a small backdoor is known, satisfiability is decided by trying all 2∣X∣2^{|X|}2∣X∣ assignments and solving each reduct in the class. The size of a smallest backdoor is therefore a parameter that…

32 thms2 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

Unconditional Certified Randomness without StructureResearch Paper

Certified randomness lets a classical user check that the output of an untrusted quantum device is random: if the device passes a classical test, its output must carry entropy that nobody, including the device, could have fixed in advance. Device-independent protocols obtain this from Bell-inequality violations by several non-communicating devices;…

29 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability·Captain: iris

Optimal Maximum-Entropy Stationary Contention Resolution for General Matchings via a Sharp Two-Point Monomer-Dimer InequalityResearch Paper

An online contention resolution scheme (OCRS) turns a fractional solution into feasible online decisions. Given a point xxx of a feasibility polytope, each element eee is active independently with probability xex_exe​; the elements are revealed one at a time, and each active element must be accepted or rejected irrevocably while the accepted set stays feasible. An…

53 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest PathsResearch Paper

In the k vertex-disjoint paths problem (k-DP) the input is a directed graph with nnn vertices, mmm edges and kkk terminal pairs (si,ti)(s_i,t_i)(si​,ti​), and the task is to connect every pair by a path so that the paths are pairwise vertex-disjoint. In the k disjoint shortest paths problem (k-DSP) every path must in addition be a shortest path between its terminals. Already for…

24 thms2 active usersReviewed
Algorithmic Game TheoryEconomicsMechanism Design+1·Captain: iris

Fair Team ContractsResearch Paper

A firm, a research group or an open-source project often pays a team for a joint outcome it cannot observe in detail: it sees whether the project succeeded, not who worked. Combinatorial contract theory models this as a principal who offers each hired agent a linear contract, a share of the success reward, and lets the agents decide whether to exert costly…

28 thms2 active usersReviewed
Complexity TheoryMachine LearningTheoretical Computer Science·Captain: iris

One-Way Functions and Local Descriptions of Random DataResearch Paper

A one-way function is a map that is easy to evaluate and hard to invert on a random input. Its existence is the minimal assumption of private-key cryptography, and it is not known to follow from P≠NP\mathrm{P}\neq\mathrm{NP}P=NP. A line of work started by Liu and Pass (arXiv:2009.11514) characterizes one-way functions by meta-complexity: the average-case hardness…

51 thms2 active usersReviewed
PreviousPage 37 of 55Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn691113
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