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.

1374 open missions

Missions

476–500 of 1374
Open1374Completed122All1496
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
Functional AnalysisOptimizationProbability·Captain: iris

New Lower and Upper Bounds for the Grothendieck ConstantResearch Paper

Grothendieck's inequality compares a bilinear form over signs with its relaxation over unit vectors. For a real matrix A=(aij)A=(a_{ij})A=(aij​), the value of ∑i,jaij⟨ui,vj⟩\sum_{i,j}a_{ij}\langle u_i,v_j\rangle∑i,j​aij​⟨ui​,vj​⟩ over unit vectors exceeds the value of ∑i,jaijεiδj\sum_{i,j}a_{ij}\varepsilon_i\delta_j∑i,j​aij​εi​δj​ over signs by at most a universal factor. The smallest such factor is the Grothendieck constant KGK_GKG​.…

56 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
Complexity TheoryTheoretical Computer Science·Captain: iris

NP-Hardness and Additive Inapproximability of Deterministic Communication ComplexityResearch Paper

Deterministic communication complexity asks how many bits two players must exchange to evaluate a Boolean function whose input is split between them. Yao introduced the model in 1979 (Yao, STOC 1979) and it has since become a basic tool for lower bounds on circuits, data structures, streaming algorithms and proof systems (Kushilevitz–Nisan, Communication…

41 thms3 active usersReviewed
Quantum Error CorrectionQuantum InformationStatistical Mechanics·Captain: iris

A passive self-correcting quantum memory in three dimensionsResearch Paper

A quantum memory stores a qubit in a many-body system. A passive self-correcting memory does this with no active error correction: the system is only coupled to a thermal bath at a fixed temperature, and its own Hamiltonian keeps the encoded qubit recoverable for a time that grows without bound with the system size. The classical analogue is the 2D Ising…

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

Optimally learning mixtures of arbitrarily many GaussiansResearch Paper

A mixture of kkk Gaussians is learned, in the classical sense, by estimating its parameters or its density. Both tasks need a number of samples that grows with kkk: with identity covariances and weights 1/k1/k1/k, Ω(k)\Omega(k)Ω(k) samples are needed just to see every component, and density estimation needs Ω(kn/ε2)\Omega(kn/\varepsilon^2)Ω(kn/ε2) samples (SOAJ14). When kkk is unbounded or…

26 thms3 active usersReviewed
Algebraic GeometryCombinatoricsInformation Theory+2·Captain: iris

Beating the Gilbert–Varshamov Bound at Alphabet Size 42Research Paper

A code C⊆ΣnC\subseteq\Sigma^nC⊆Σn is a set of words of length nnn over a finite alphabet Σ\SigmaΣ of size qqq. Its rate log⁡q∣C∣/n\log_q|C|/nlogq​∣C∣/n measures information per symbol, and its relative minimum distance δ\deltaδ is the smallest fraction of coordinates on which two distinct codewords differ. The tradeoff between rate and distance is the oldest question of coding theory (Shannon…

38 thms3 active usersReviewed
CombinatoricsLinear OptimizationOptimization·Captain: iris

A Sharp Mean-Budget Transition for Local Pair MarginalsResearch Paper

Local-consistency relaxations describe the low-order statistics of Boolean variables through probability laws on overlapping small sets of variables. The laws must agree on overlaps but need not be marginals of one joint distribution. Such relaxations are standard in constraint satisfaction and polynomial optimization, going back to the hierarchy of Sherali…

58 thms3 active usersReviewed
Convex OptimizationNumerical AnalysisOptimization+1·Captain: iris

Solving ppp-norm regression in matrix multiplication timeResearch Paper

Given a matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d of full column rank and a vector b∈Rnb\in\mathbb R^nb∈Rn, ℓp\ell_pℓp​ regression asks for a minimizer of ∥Ax−b∥p\|Ax-b\|_p∥Ax−b∥p​. The case p=2p=2p=2 is least squares; p∈{1,∞}p\in\{1,\infty\}p∈{1,∞} is equivalent to linear programming; the values in between interpolate between linear system solving and linear programming and arise in data analysis and in flow…

34 thms3 active usersReviewed
Linear algebraNumerical AnalysisOptimization·Captain: iris

Global Sinkhorn Convergence and Spectral Stability of Matrix ScalingResearch Paper

Matrix scaling asks for positive diagonal matrices X,YX,YX,Y that turn a nonnegative square matrix AAA into a matrix XAYXAYXAY with prescribed row and column sums; here the target is a doubly stochastic matrix. Classical uses include adjusting contingency tables to given marginal totals (Deming and Stephan, 1940), and a prominent modern one is entropically regularized…

31 thms3 active usersReviewed
Complexity TheoryInformation TheoryOperations Research+1·Captain: iris

On Global Joint Lower Bounds in Zeroth-Order Nonconvex OptimizationResearch Paper

Many optimization problems give access only to function values: simulation-based design, hyperparameter tuning, black-box attacks, reinforcement learning with policy evaluations. In the stochastic version, the objective is an average f=∣Ξ∣−1∑ξfξf=|\Xi|^{-1}\sum_{\xi}f_\xif=∣Ξ∣−1∑ξ​fξ​ of sample functions, and an algorithm pays one unit for each exact value fξ(x)f_\xi(x)fξ​(x). For smooth…

37 thms3 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: iris

Optimal Law-Local Compression for Stochastic LoadsResearch Paper

Stochastic scheduling and load balancing evaluate a random load vector L=∑jXjajL=\sum_j X_ja_jL=∑j​Xj​aj​, where job jjj has an independent random size XjX_jXj​ and a fixed nonnegative direction aja_jaj​ (for instance, the machine it is assigned to), through an expected norm Eg(L)\mathbb E g(L)Eg(L): the expected makespan, an expected top-ℓ\ellℓ sum, or any other monotone norm. Algorithms for these…

73 thms3 active usersReviewed
PreviousPage 20 of 55Next

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