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

501–525 of 1496
Open1374Completed122All1496
CombinatoricsGraph TheoryProbability·Captain: iris

List Coloring Uncrowded Hypergraphs at the Shattering ThresholdResearch Paper

How many colors does a sparse hypergraph need? For graphs, the greedy bound χ(G)≤Δ+1\chi(G)\le\Delta+1χ(G)≤Δ+1 can be improved by a factor of log⁡Δ\log\DeltalogΔ when short cycles are excluded. Kim proved χℓ(G)≤(1+o(1))Δ/log⁡Δ\chi_\ell(G)\le(1+o(1))\Delta/\log\Deltaχℓ​(G)≤(1+o(1))Δ/logΔ for graphs of girth at least 555 (Kim, 1995), and Johansson and Molloy extended the Δ/log⁡Δ\Delta/\log\DeltaΔ/logΔ rate to triangle-free graphs…

30 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: iris

Claw-free perfect graphs are chromatic-choosable.Research Paper

List colouring was introduced by Vizing (1976) and by Erdős, Rubin and Taylor (1980): every vertex receives its own list of admissible colours, and a colouring must pick from each list. The choice number ch(G)\mathrm{ch}(G)ch(G) is the least kkk for which lists of size kkk always suffice. Since all lists may be equal, ω(G)≤χ(G)≤ch(G)\omega(G) \le \chi(G) \le \mathrm{ch}(G)ω(G)≤χ(G)≤ch(G), and GGG is chr…

34 thms3 active usersReviewed
Algorithmic Game TheoryGraph TheoryTheoretical Computer Science·Captain: iris

The Caccetta-Häggkvist Conjecture and Percentile Distortion: An Equivalence via Asymmetric Maximal LotteriesResearch Paper

Metric distortion measures how much a voting rule loses by seeing only ordinal preferences. Voters and candidates sit in an unknown metric space; each voter ranks candidates by distance, and the rule sees only the rankings. The distortion of a rule is the worst case, over elections and over metrics consistent with the rankings, of the ratio between the cost…

45 thms3 active usersReviewed
Complexity TheoryGraph TheoryQuantum Information+1·Captain: iris

Quantum Advantage in Local Certification of Graph PropertiesResearch Paper

In local certification, an untrusted prover (Merlin) assigns a certificate to every node of a network. The nodes then exchange messages with their neighbours for a fixed number of rounds and each node decides to accept or reject; the network accepts when all nodes accept. The resource measured is the certificate size per node. This model underlies…

34 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

A Constant-Factor Approximation for Capacitated Facility Location with OutliersResearch Paper

In facility location a planner opens facilities, each with an opening cost, and assigns clients to open facilities, paying the distance as service cost. Two standard extensions model practical constraints. In capacitated facility location (CFL) each facility serves at most uiu_iui​ clients and can be opened at most once (hard capacities). In facility location…

28 thms3 active usersReviewed
AlgebraComplexity TheoryInformation Theory+1·Captain: iris

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes and Variants, via Non-Archimedean RingsResearch Paper

Reed–Solomon codes are the basic family of algebraic error-correcting codes: a message is a polynomial of degree below kkk over a finite field Fq\mathbb F_qFq​, and the codeword is its list of values at nnn distinct points. For a code of rate R=k/nR=k/nR=k/n, three radii organize decoding: the unique-decoding radius (1−R)/2(1-R)/2(1−R)/2, the Johnson radius 1−R1-\sqrt R1−R​, and the covering…

26 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: iris

Algorithmic Aspects of the Fermi–Hubbard ModelResearch Paper

The Fermi–Hubbard model is the standard minimal model of interacting electrons on a lattice. Each site holds up to two electrons (spin up and spin down); electrons hop between neighbouring sites with amplitude tijt_{ij}tij​, pay an energy UiU_iUi​ when two of them share a site, and feel a chemical potential μi\mu_iμi​. Its phase diagram (Mott insulators, antiferromagnetism,…

37 thms3 active usersReviewed
Complexity TheoryOptimizationQuantum Information+1·Captain: iris

What can be Computed with Indefinite Causal Structure?Research Paper

Quantum mechanics allows the order in which operations act to be in superposition. The process matrix formalism of Oreshkov, Costa and Brukner (OCB12) describes such situations: several laboratories each apply a local quantum operation, and a process matrix WWW fixes how their inputs and outputs are wired, without assuming a global causal order. Araújo, Feix,…

34 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

From Succinct Arguments to Proofs: Lower Bounds for Obfuscation and SNARGsResearch Paper

Indistinguishability obfuscation (iO) and witness encryption (WE) are among the most powerful primitives in cryptography: iO implies almost every known cryptographic object, and WE lets anyone encrypt a message so that only a holder of an NP witness for a public statement can read it (Garg, Gentry, Halevi, Raykova, Sahai, Waters 2013; Garg, Gentry, Sahai,…

63 thms3 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

A Resolution of Friedgut's Conjecture on Influential CoalitionsResearch Paper

A coalition of coordinates of a Boolean function is influential if, after the other coordinates are drawn at random, its members can choose their own values so as to force the output. The question comes from collective coin flipping, introduced by Ben-Or and Linial (FOCS 1985): in a one-round protocol with independent uniform messages, a coalition is a set…

22 thms3 active usersReviewed
Harmonic AnalysisMachine LearningProbability+2·Captain: iris

Learning Mixtures with Unknown Scales: Sharp Dependence on SeparationResearch Paper

Finite mixture models describe a heterogeneous population as a weighted combination of component distributions. Recovering the locations, scales and weights of the components from samples is a central problem in statistics and learning theory, with a long line of work on Gaussian mixtures and other parametric families (Kalai, Moitra, Valiant 2010; Moitra,…

27 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

Polynomial-Time Approximate EFX for Chores via Flow and MatchingResearch Paper

Fair allocation of indivisible chores asks how to divide burdens among agents whose costs for those burdens differ. It is studied in algorithmic game theory and social choice (Aziz, Li, Moulin, Wu, 2022). The natural target is envy-freeness up to any chore (EFX): an agent's envy must disappear after any single chore is removed from her own bundle. Exact EFX…

29 thms3 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

The Contraction Lemma Beyond ETH: Algorithms and Lower BoundsResearch Paper

The Exponential Time Hypothesis of Impagliazzo and Paturi says that 3-SAT on nnn variables needs time 2Ω(n)2^{\Omega(n)}2Ω(n). Hundreds of conditional lower bounds in fine-grained complexity rest on it. In October 2026 two manuscripts refuted it: OpenAI's The Exponential Time Hypothesis is false and Anthropic's A 2o(n)2^{o(n)}2o(n) time algorithm for 3-SAT. Both give…

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

The Communication Complexity of Verifying Distribution PropertiesResearch Paper

An untrusted analyst holds many samples from an unknown distribution over [N][N][N] and claims that the distribution has some property: for example, that it is close to uniform or has large support. Interactive proofs for distribution properties (Chiesa–Gur 2018, following Goldwasser–Micali–Rackoff) let a verifier with few samples check such a claim by talking to…

26 thms3 active usersReviewed
CombinatoricsQuantum InformationRepresentation Theory+1·Captain: iris

Compressed Permutation Oracles RevisitedResearch Paper

Random permutations and ideal ciphers model the primitives inside sponge hashing (SHA-3) and the Davies–Meyer compression function (SHA-1, SHA-2). A quantum adversary may query them in superposition, in both directions, which makes the information gained by its queries hard to track. For random functions, Zhandry's compressed oracle represents an oracle's…

33 thms3 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: iris

Optimal Online Bin Covering across Stochastic ModelsResearch Paper

In bin covering, items with sizes in (0,1](0,1](0,1] are assigned to bins, and a bin counts when the items in it have total size at least 111. The problem models threshold objectives: packages that must reach a minimum weight, batches that must reach a minimum volume. Its offline theory parallels bin packing with the objective reversed. Assmann, Johnson, Kleitman and…

35 thms3 active usersReviewed
Category TheoryComplexity TheoryGraph Theory+1·Captain: iris

Co-Decompositions and FO Model CheckingResearch Paper

First-order model checking is the problem of deciding whether a structure satisfies a first-order sentence. It is the standard test of algorithmic meta-theorems. Tractability results for it include those of Frick and Grohe on locally tree-decomposable structures and of Bonnet, Kim, Thomassé and Watrigant for bounded twin-width. In these results the…

28 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

The Hyperclique Hypothesis is FalseResearch Paper

Fine-grained complexity explains why many polynomial-time problems resist faster algorithms by reducing them from a few hardness hypotheses. One of these is the Hyperclique Hypothesis of Lincoln, Vassilevska Williams and Williams (LVW18): for all constants k>h≥3k > h \ge 3k>h≥3 and ϵ>0\epsilon > 0ϵ>0, a kkk-clique in an hhh-uniform hypergraph with nnn vertices cannot be detected…

35 thms3 active usersReviewed
Graph TheoryLinear algebraProbability+1·Captain: iris

Incremental All-Pairs Effective Resistance in Almost-Linear TimeResearch Paper

The effective resistance between two vertices of a graph with edge conductances is the energy of the electrical flow that sends one unit of current between them. More generally, a demand d∈RVd\in\mathbb R^Vd∈RV with zero sum has energy d⊤LG†dd^\top L_G^\dagger dd⊤LG†​d, where LGL_GLG​ is the graph Laplacian. These quantities drive spectral sparsification (Spielman–Srivastava, SIAM…

35 thms3 active usersReviewed
CombinatoricsInformation TheoryQuantum Error Correction+1·Captain: iris

Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure ChannelsResearch Paper

Quantum information is lost in a quantum erasure channel when a qubit is damaged at a known location, for example by atom loss or photon loss. Each of NNN qubits is erased independently with probability ρ\rhoρ, and the decoder knows the set of erased positions. The capacity of this channel is 1−2ρ1-2\rho1−2ρ for 0≤ρ<1/20\le\rho<1/20≤ρ<1/2 (Bennett, DiVincenzo, Smolin 1997).…

28 thms3 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research+1·Captain: iris

The Existence of Maximin Share Allocations is Δ2P\Delta_2^PΔ2P​-completeResearch Paper

The maximin share (MMS) is a fairness benchmark for dividing indivisible goods among agents with different valuations. Agent iii's maximin share is the best value she could guarantee if she split all the goods into nnn bundles herself and then received the worst bundle. An allocation that gives every agent at least her maximin share is an MMS allocation. The…

40 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationRepresentation Theory·Captain: iris

Optimal testing of fermionic and bosonic Gaussian statesResearch Paper

Quantum property testing asks how many copies of an unknown pure state ∣ψ⟩|\psi\rangle∣ψ⟩ are needed to decide whether ψ\psiψ belongs to (or is close to) a given class C\mathcal CC, or is far from it. The question is most interesting when the answer does not grow with the size of the system: learning a state of nnn modes generally needs a number of copies that grows…

45 thms3 active usersReviewed
Harmonic AnalysisOptimizationProbability+1·Captain: iris

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation HierarchyResearch Paper

Maximizing a homogeneous polynomial PPP of degree ddd over the unit sphere, ∥P∥∞=max⁡x∈Sn−1∣P(x)∣\|P\|_\infty=\max_{x\in S^{n-1}}|P(x)|∥P∥∞​=maxx∈Sn−1​∣P(x)∣, is the spectral norm of a symmetric tensor. It is NP-hard already for order-three tensors (Hillar–Lim 2013), so the useful questions are approximation and certification: find a tractable upper bound and measure how far it can be from the truth.

49 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra·Captain: iris

On Brouwer's Laplacian conjectureResearch Paper

The Laplacian L=D−AL=D-AL=D−A of a graph records its degrees on the diagonal and its edges off it. Its spectrum controls connectivity, expansion, random walks, cuts and spanning trees, and sums of its largest eigenvalues appear in graph partitioning and in the energy of quadratic forms over a graph. A natural question is how large the top of the spectrum can be in…

19 thms3 active usersReviewed
Algorithmic Game TheoryProbabilityTheoretical Computer Science·Captain: iris

Nash Equilibria, Variational Inequalities, and Fixed Points: Beating Brute Force via Smoothed AnalysisResearch Paper

Computing a Nash equilibrium of a finite game is a basic problem of algorithmic game theory, and in the worst case it is hard: finding an approximate equilibrium of a normal-form game is PPAD-complete even for two players (Daskalakis–Goldberg–Papadimitriou 2009; Chen–Deng–Teng 2009), and under the exponential time hypothesis even constant-approximate…

43 thms3 active usersReviewed
PreviousPage 21 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