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

601–625 of 1499
Open1321Completed178All1499
Computational GeometryGraph TheoryProbability+1·Captain: iris

Deterministic Approximate Nearest Neighbors in High DimensionsResearch Paper

In the (1+ε)(1+\varepsilon)(1+ε)-approximate nearest-neighbor problem ((1+ε)(1+\varepsilon)(1+ε)-ANN) a set PPP of nnn points of Rd\mathbb R^dRd is preprocessed into a data structure, and each later query q∈Rdq\in\mathbb R^dq∈Rd must be answered by a point x^∈P\hat x\in Px^∈P with ∥q−x^∥2≤(1+ε)min⁡x∈P∥q−x∥2\|q-\hat x\|_2\le(1+\varepsilon)\min_{x\in P}\|q-x\|_2∥q−x^∥2​≤(1+ε)minx∈P​∥q−x∥2​. It is a basic primitive of similarity search, clustering and…

75 thms3 active usersReviewed
Quantum InformationStatisticsTheoretical Computer Science·Captain: iris

Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurementsResearch Paper

Quantum state tomography produces a classical description of an unknown quantum state from measurements on copies of it. For an nnn-qubit pure state ∣ψ⟩∈Cd|\psi\rangle \in \mathbb C^d∣ψ⟩∈Cd, d=2nd = 2^nd=2n, the optimal number of copies for infidelity 1−∣⟨ψ^∣ψ⟩∣2≤ϵ1 - |\langle\hat\psi|\psi\rangle|^2 \le \epsilon1−∣⟨ψ^​∣ψ⟩∣2≤ϵ at constant failure probability is Θ(d/ϵ)\Theta(d/\epsilon)Θ(d/ϵ), and it is already…

44 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Using Small Advice to Compress the Predecessor MatrixResearch Paper

The predecessor matrix of a directed graph stores, for every ordered pair (u,v)(u,v)(u,v), the vertex immediately before vvv on a shortest uuu–vvv path. Repeated lookups recover a shortest path backward in O(1)O(1)O(1) time per edge, and the matrix takes Θ(n2log⁡n)\Theta(n^2\log n)Θ(n2logn) bits. For unweighted graphs, distances alone admit far more compact exact representations: O(n2)O(n^2)O(n2) bits with…

36 thms3 active usersReviewed
Complexity TheoryMathematical LogicTheoretical Computer Science·Captain: iris

Backdoors for Quantified Boolean FormulasResearch Paper

A quantified Boolean formula (QBF) Φ=Q.ϕ\Phi = Q.\phiΦ=Q.ϕ quantifies every variable of a Boolean matrix ϕ\phiϕ by a prefix Q=Q1x1⋯QnxnQ = Q_1x_1\cdots Q_nx_nQ=Q1​x1​⋯Qn​xn​, Qi∈{∀,∃}Q_i\in\{\forall,\exists\}Qi​∈{∀,∃}. Deciding its truth is the canonical PSPACE-complete problem. It is the natural target for problems in verification, planning and non-monotonic reasoning that lie above NP.

23 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Randomized Greedy MIS is Fast at Every NodeResearch Paper

A local computation algorithm answers a query about one part of a global solution (here: is vertex vvv in the maximal independent set?) by inspecting only a small neighbourhood of vvv, so that answers to different queries are consistent with one global solution. Nguyen and Onak (FOCS 2008) simulated the randomized greedy maximal independent set (RGMIS) this…

41 thms3 active usersReviewed
Numerical AnalysisProbabilityRandom Matrix Theory+1·Captain: iris

From smoothed analysis to backward error: The power of adaptive perturbationsResearch Paper

A backward-stable solution of a linear system Ax=bAx=bAx=b is a vector x~\tilde xx~ that solves a nearby system exactly: (A+Δ)x~=b(A+\Delta)\tilde x=b(A+Δ)x~=b with ∥Δ∥2≤ε∥A∥2\|\Delta\|_2\le\varepsilon\|A\|_2∥Δ∥2​≤ε∥A∥2​. Backward error is the standard accuracy notion of numerical linear algebra, and it makes sense even when AAA is singular or badly conditioned. A natural way to obtain it is borrowed from smoot…

32 thms3 active usersReviewed
Complexity TheoryGroup TheoryTheoretical Computer Science·Captain: iris

Truly Subquadratic 3SUM over Every Bounded-Exponent Abelian GroupResearch Paper

Three-list 3SUM asks whether x1+x2+x3=0x_1+x_2+x_3=0x1​+x2​+x3​=0 for some xix_ixi​ in three given lists. It is a central problem of fine-grained complexity, and truly subquadratic algorithms for it over the integers have recently been obtained through the thin-matrix-product algorithm of Alman and Vassilevska Williams (arXiv:2610.06783v1); another route is due to Chan, Itakura, Ma…

22 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Four-Coloring Planar Graphs in Linear TimeResearch Paper

The Four Color Theorem says that every planar graph has a proper coloring with four colors. It asks for existence. Whoever needs a coloring of a concrete graph needs an algorithm, and all known algorithms pass through the machinery of the proof: reducible configurations and Kempe changes. Formal verification has followed the same line: the theorem was…

36 thms3 active usersReviewed
Number TheoryProbabilityTheoretical Computer Science·Captain: iris

Provable Recovery from Integer Quotients: Improved Bounds for Nonlinear Hidden Number ProblemsResearch Paper

A hidden number problem asks whether a secret can be recovered from partial information about values algebraically linked to it. In cryptography these problems measure what leaked bits of secret values or internal randomness are worth, and they underlie security analyses and key-recovery attacks. The modular inversion hidden number problem (MIHNP),…

28 thms3 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: iris

Efficient Private and Robust StatisticsResearch Paper

A differentially private estimator has an output law that barely changes when one sample is swapped. A robust estimator stays accurate when a small fraction of its samples has been replaced by an adversary. Both requirements limit the influence of individual samples, so they look compatible, and information-theoretic algorithms achieving both exist.…

28 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: iris

Almost-MMS allocations with small agent redundancyResearch Paper

The maximin share (MMS), introduced by Budish (JPE 2011), is the standard share-based fairness notion for indivisible goods: an agent's benchmark is the value that agent could guarantee by splitting all the goods into as many bundles as there are agents and receiving the worst one. Exact MMS allocations need not exist for additive agents (Kurokawa,…

35 thms3 active usersReviewed
Computational GeometryGraph TheoryProbability+1·Captain: iris

Sparse α\alphaα-Navigable Graphs in Euclidean Space via Steiner PointsResearch Paper

Most practical systems for approximate nearest neighbor search in high dimension store the data set P⊂RdP\subset\mathbb R^dP⊂Rd as a directed graph and answer a query qqq by greedy search: starting at some vertex, as long as an out-neighbor of the current vertex is closer to qqq than the current vertex is, move to the out-neighbor closest to qqq; when no such neighbor…

23 thms3 active usersReviewed
CombinatoricsProbabilityRandom Matrix Theory+1·Captain: iris

A Proof of the Matrix Spencer ConjectureResearch Paper

Discrepancy theory asks how evenly a family of objects can be split by signs. Spencer's "six standard deviations suffice" theorem (Trans. AMS, 1985) says that for vectors a1,…,an∈Rda_1,\dots,a_n\in\mathbb R^da1​,…,an​∈Rd with ∥ai∥∞≤1\|a_i\|_\infty\le1∥ai​∥∞​≤1 there are signs with ∥∑ixiai∥∞≤O(nmax⁡{1,log⁡(d/n)})\|\sum_ix_ia_i\|_\infty\le O(\sqrt n\sqrt{\max\{1,\log(d/n)\}})∥∑i​xi​ai​∥∞​≤O(n​max{1,log(d/n)}​), which beats the bound a random coloring gives. The…

54 thms3 active usersReviewed
Computational ComplexityGraph TheoryProbability+1·Captain: iris

Puncturable Graph Sketches and the Complexity of Distributed Vertex ConnectivityResearch Paper

Deciding how strongly a graph is connected is a basic problem in combinatorics and network analysis. A graph is kkk-connected if deleting fewer than kkk of its vertices leaves a connected graph with at least two vertices. With the whole graph in hand this is solved in m1+o(1)m^{1+o(1)}m1+o(1) time by maximum-flow computations. The question changes when no single machine…

60 thms3 active usersReviewed
Convex OptimizationProbabilityRandom Matrix Theory+1·Captain: iris

Sharp Phase Transition for Ellipsoid FittingResearch Paper

Given mmm random points in Rd\mathbb R^dRd, is there a centered ellipsoid through all of them? This ellipsoid fitting problem was introduced by Saunderson (PhD thesis, MIT, 2011) and studied by Saunderson, Chandrasekaran, Parrilo and Willsky (2012) in connection with decomposing a matrix into a diagonal and a low-rank part. It is also a basic test case for…

29 thms3 active usersReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

Subexponential Upper Bounds for 3-Restricted Matching Vector FamiliesResearch Paper

A locally decodable code recovers any one message symbol, with high probability, from a constant number rrr of positions of a possibly corrupted codeword. The central question is how short a codeword can be for a fixed rrr. For r=2r=2r=2 the Hadamard code is optimal up to a constant factor. For r≥3r\ge3r≥3 the gap is wide: the best general lower bound for r=3r=3r=3 is near-cubic…

29 thms3 active usersReviewed
Complexity TheoryOperations ResearchProbability+1·Captain: iris

Computational Hardness of Online Stochastic MatchingResearch Paper

In online stochastic matching, offline resources (ads, drivers, servers) are matched irrevocably to online requests that arrive one at a time with random types drawn from known distributions. The known i.i.d. model of Feldman, Mehta, Mirrokni and Muthukrishnan (2009) draws every request from the same distribution. Most of the literature compares online…

30 thms3 active usersReviewed
Computational GeometryProbabilityTheoretical Computer Science·Captain: iris

Estimating the Volume of a Union of Convex BodiesResearch Paper

Computing the volume of a single convex body in Rn\mathbb R^nRn is #P-hard, yet randomized algorithms approximate it to relative error ε\varepsilonε in polynomial time from a membership oracle (Dyer–Frieze–Kannan 1991; Cousins–Vempala 2018). A union of convex bodies is not convex, so these algorithms do not apply to it directly. Unions arise in Klee's measure…

40 thms3 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: iris

Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit GatesResearch Paper

A pseudorandom unitary is an efficiently implementable family of unitaries that no efficient quantum algorithm with query access can tell apart from a Haar-random unitary. Ji, Liu and Song introduced the notion in 2018 as the quantum analogue of a pseudorandom function (JLS18), and Ma and Huang constructed pseudorandom unitaries from any quantum-secure…

56 thms3 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Explicit functions requiring larger than 4.5n size circuitsResearch Paper

A B2B_2B2​-circuit is a Boolean circuit in which every gate has fan-in two and may compute any of the sixteen binary Boolean functions. Whether P\mathbf PP has circuits of size k⋅nk \cdot nk⋅n for some constant kkk is a long-standing open question; no superlinear lower bound for an explicit function is known. Even the constant in front of nnn has moved slowly, and every…

53 thms3 active usersReviewed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: iris

Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short BroadcastsResearch Paper

A dominating set of a graph GGG is a set DDD of vertices such that every vertex lies in DDD or has a neighbour in DDD. In a distributed network the graph is also the communication medium, so an algorithm that computes DDD must decide locally, from what the vertices can exchange in a few rounds. Approximating the minimum dominating set in a constant number of rounds…

35 thms3 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: iris

A Better-than-e1/ee^{1/e}e1/e Approximation Algorithm for Nash Social Welfare under Additive ValuationsResearch Paper

Dividing indivisible goods among agents is a basic problem in fair division and in the design of allocation mechanisms. Among the objectives one can maximize, the Nash social welfare (the geometric mean of the agents' utilities) is singled out because it balances efficiency and fairness: it is scale-invariant in each agent's valuation and its maximizers…

90 thms3 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

No Perfect Randomized CompositionResearch Paper

Suppose an algorithm must evaluate a Boolean function fff, but each input bit of fff is itself the output of a Boolean function ggg on a separate block of bits. The natural algorithm runs a bounded-error algorithm for ggg whenever it needs a bit of fff. Writing R\mathrm{R}R for bounded-error randomized query complexity, the randomized composition question asks whether…

56 thms3 active usersReviewed
AlgebraComplexity TheoryLinear algebra+2·Captain: iris

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fieldsResearch Paper

Tensor Isomorphism (TI) asks whether two 3-way arrays over a field are related by invertible changes of basis along their three directions. A family of problems is polynomial-time equivalent to it: isomorphism of algebras given by structure constants, conjugacy of matrix codes, isomorphism of ppp-groups of class 2 and exponent ppp, and others (Grochow–Qiao,…

38 thms3 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

Strategyproof Aggregation in Euclidean Spaces: Rigidity and Median OptimalityResearch Paper

In single-facility location, nnn agents report ideal points x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb R^dx1​,…,xn​∈Rd and a mechanism selects one location yyy. Each agent's cost is its Euclidean distance ∥xi−y∥\|x_i-y\|∥xi​−y∥, and the planner wants to keep the total distance small. Agents may misreport, so the mechanism is required to be strategyproof: no agent can move the outcome closer to its true…

46 thms3 active usersReviewed
PreviousPage 25 of 60Next

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