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

201–225 of 1496
Open1377Completed119All1496
Computational ComplexityQuantum Information·Captain: iris

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified RandomnessResearch Paper

Random circuit sampling experiments are at present the leading demonstrations of quantum computational advantage (Arute et al., 2019). The samples of such an experiment are scored by the linear cross-entropy benchmark, which rewards an output in proportion to the probability that the ideal circuit assigns to it. A device that knew the ideal distribution…

31 thms4 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

From Computational Nonlocality to Public-Key Encryption and CommitmentsResearch Paper

Public-key encryption is usually built from structured hardness assumptions such as factoring or learning with errors. In the quantum world one may ask for weaker foundations: protocols in which the honest parties are quantum computers that exchange only classical messages (QCCC, quantum computation with classical communication), and whose security rests on…

81 thms4 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private FilteringResearch Paper

A differentially private release adds noise calibrated to how much one record can move the output. Worst-case (global) sensitivity is often far larger than the influence of a record in typical data: a single outlier can force noise that is out of proportion to every other record. Several lines of work scale noise to the data instead, including smooth…

31 thms4 active usersReviewed
CombinatoricsQuantum InformationTheoretical Computer Science·Captain: iris

Spectrum Estimation is Almost as Hard as TomographyResearch Paper

A ddd-dimensional quantum state is a density matrix ρ∈Cd×d\rho\in\mathbb C^{d\times d}ρ∈Cd×d: positive semidefinite with trace 111. Its eigenvalues form a probability distribution, the spectrum of ρ\rhoρ, which determines every unitarily invariant property of the state: its von Neumann entropy, its purity, its rank. Spectrum estimation asks how many identical copies of an…

51 thms4 active usersReviewed
Harmonic AnalysisNumber TheoryProbability+1·Captain: iris

When Masks Leak Their Weight: From Additive Sharing to Learning with Physical RoundingResearch Paper

Masking protects a secret held by a physical device by splitting it into random additive shares that sum to the secret modulo NNN; each share alone is uniformly distributed. In practice the device leaks a noisy function of every share it touches, and the standard model of that leakage on CMOS hardware is the Hamming weight of the share: the number of ones in…

41 thms4 active usersReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: iris

Revisiting the XOR lemmaResearch Paper

Yao's XOR lemma is a basic hardness-amplification result in complexity theory: if a Boolean function fff has correlation at most ϵ\epsilonϵ with every circuit of size sss, then the XOR of kkk independent copies of fff has correlation about ϵk\epsilon^kϵk with circuits of size close to sss (Goldreich–Nisan–Wigderson 1995). It is used throughout pseudorandomness,…

23 thms4 active usersReviewed
Complexity TheoryConvex OptimizationGraph Theory+2·Captain: iris

Asymptotic Rank of Weighted Graph Tensors via Completely Positive CoversResearch Paper

The asymptotic rank of a tensor measures how cheaply many copies of it can be computed together. For the triangle graph tensor it is the matrix multiplication exponent: log⁡2R~F(GT2(K3))=ωF\log_2\tilde R_{\mathbb F}(\mathsf{GT}_2(K_3))=\omega_{\mathbb F}log2​R~F​(GT2​(K3​))=ωF​ over every field F\mathbb FF (Bürgisser–Clausen–Shokrollahi 1997, Prop. 15.1). Graph tensors extend this object from three…

39 thms4 active usersReviewed
Information TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Dimension-Free Polylogarithmic Quantum Shadow TomographyResearch Paper

Measuring a quantum state disturbs it, so copies are the resource that any learning task consumes. Shadow tomography, introduced by Aaronson (STOC 2018), asks how many copies of an unknown state suffice to predict the expectation values of many known measurements, without reconstructing the state. The question matters in quantum learning theory and in the…

38 thms4 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory+1·Captain: iris

Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum BisectionResearch Paper

In Minimum Bisection, the input is a graph GGG on nnn vertices and an integer kkk, and the question is whether V(G)V(G)V(G) can be split into sets of sizes ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ and ⌈n/2⌉\lceil n/2\rceil⌈n/2⌉ with at most kkk edges between them. The problem is NP-hard, and it has been a central test case for parameterized cut problems because its constraint is global: whether part of a…

38 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: iris

On Existence and Computational Complexity of Quasi-strict EquilibriaResearch Paper

A Nash equilibrium of a two-player game may leave some best responses unplayed: a player is indifferent between several pure strategies and puts weight on only some of them. Harsanyi (1973) introduced quasi-strict equilibria, the refinement in which every pure best response is played with positive probability, and proved that in almost all finite games…

80 thms4 active usersReviewed
ProbabilityRandom Matrix TheoryStatistics+1·Captain: iris

Efficient Posterior Sampling for Z2\mathbb Z_2Z2​ SynchronizationResearch Paper

Z2\mathbb Z_2Z2​ synchronization is the simplest spiked random-matrix model: an unknown sign vector is observed through a rank-one perturbation of a symmetric Gaussian matrix. It is a standard test case in high-dimensional statistics and probability (Johnstone, On the distribution of the largest principal component, 2000). For the normalization below, λ=1\lambda=1λ=1 i…

32 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Online Matching with Arbitrary Stochastic RewardsResearch Paper

In online bipartite matching a set of offline resources is known in advance and arrivals are revealed one at a time; each arrival must be matched irrevocably on arrival. Karp, Vazirani and Vazirani showed that the randomized Ranking algorithm is (1−1/e)(1-1/e)(1−1/e)-competitive and that no online algorithm does better [KVV90]. Motivated by pay-per-click advertising,…

33 thms4 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUTResearch Paper

MAX-3-CUT asks for the partition of the vertices of a finite undirected graph into three sets that maximizes the number of edges joining different sets. It is the three-colour version of MAX-CUT and is equivalent to the Maximum 3-Colorable Subgraph problem. A random assignment of vertices cuts 2/32/32/3 of the edges in expectation. Frieze and Jerrum (1997) general…

70 thms4 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

Low-Temperature Sampling via Equilibrium DisagreementsResearch Paper

Sampling from a Gibbs distribution at low temperature is a basic task in counting, statistical physics and Bayesian inference, and it is hard for a structural reason. At low temperature the distribution splits into several phases, regions of the state space that each carry a large share of the mass and are separated by bottlenecks. Glauber dynamics, the…

32 thms4 active usersReviewed
AlgebraCombinatoricsComplexity Theory+1·Captain: iris

On Robust Promise CSPs: A Boolean Dichotomy, Sharp Quantitative Bounds, and Soft-Equality TransferResearch Paper

A promise constraint satisfaction problem (PCSP) asks, given an instance that is satisfiable with respect to a strong family of relations, for an assignment satisfying a weaker family. Its robust version asks for more: when some assignment violates only an ϵ\epsilonϵ fraction of the strong constraints, an algorithm must return an assignment that violates at…

57 thms4 active usersReviewed
Harmonic AnalysisInformation TheoryProbability+1·Captain: iris

A Nonadaptive Sparse Fourier Transform in Every DimensionResearch Paper

A sparse Fourier transform recovers the few large Fourier coefficients of a signal from far fewer samples than the signal's length, and in time polynomial in the number of coefficients rather than in the length. It is used whenever a spectrum is dominated by a small number of frequencies and reading the whole signal is expensive. The standard accuracy…

24 thms4 active usersReviewed
Quantum Error CorrectionQuantum InformationTheoretical Computer Science·Captain: iris

Quantum Pseudorandom Error-Correcting CodesResearch Paper

A pseudorandom error-correcting code (PRC) is a keyed code whose codewords look uniformly random to anyone without the key, yet decode correctly after noise. Christ and Gunn introduced classical PRCs to watermark the outputs of generative models: a watermark must be invisible to an observer and must survive edits (CG24). Hsieh and Yamada ask for the quantum…

40 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Finite-Memory Search: Rational Compilation and Arithmetic Lower BoundsResearch Paper

A searcher repeatedly examines two locations, AAA and BBB, until it finds a stationary target. A search at the correct location fails with a known probability; a search at the wrong location always fails, and before success the searcher observes nothing but failure. The unrestricted problem is classical: greedy index rules go back to Blackwell and to Matula (Mat…

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

Gaussian Partitioning for Reliable Learning of Multi-Index ModelsResearch Paper

Many learning algorithms for Boolean functions on Rd\mathbb R^dRd rest on properties of the standard Gaussian: low-degree polynomial approximation, moment bounds, Hermite analysis. In several settings the examples a learner sees are not Gaussian even when the original input distribution is. Boosting reweights the examples during its run; a learner given only…

47 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

A 2.81n2.81^n2.81n upper bound on the number of stable matchingsResearch Paper

A stable matching instance has nnn men and nnn women, each ranking the other side strictly. Gale and Shapley showed that a stable matching always exists (1962). How many there can be is a question Knuth posed in 1976, and it is listed among the open problems of Gusfield and Irving (1989), Manlove (2013) and Cechlárová, Cseh and Manlove (2019). The answer…

25 thms4 active usersReviewed
Graph TheoryMathematical LogicTheoretical Computer Science·Captain: iris

Model Checking for Metric Extensions of Monadic Second-Order LogicResearch Paper

Courcelle's theorem is the standard tool for showing that a graph problem is tractable on tree-like graphs: every property expressible in counting monadic second-order logic can be decided in time f(∣φ∣+tw(G))NO(1)f(|\varphi|+\mathrm{tw}(G))N^{O(1)}f(∣φ∣+tw(G))NO(1) (Courcelle 1992; Arnborg, Lagergren, Seese 1991). Optimization and counting versions followed (Courcelle, Mosbah 1993), as did…

49 thms4 active usersReviewed
CombinatoricsGraph TheoryQuantum Error Correction+1·Captain: iris

Linear-time erasure recovery for quantum expander codesResearch Paper

An erasure is a fault whose location is known: a qubit that has leaked out of its computational subspace, a lost photon, or a heralded atom loss is flagged, and the decoder receives the set L\mathcal LL of flagged qubits together with the syndrome of the unknown error E⊆LE\subseteq\mathcal LE⊆L. Several hardware platforms (neutral atoms, superconducting dual-rail…

37 thms4 active usersReviewed
Complexity TheoryProbabilityQuantum Information+1·Captain: iris

Verifiable quantum advantage based on polynomials with planted structuresResearch Paper

Random-circuit sampling experiments claim quantum advantage by producing samples that a classical computer cannot produce in reasonable time. The usual test, the linear cross-entropy benchmark (XEB), scores samples by their ideal output probabilities, and computing those probabilities is as hard as simulating the circuit. Every such experiment therefore…

46 thms4 active usersReviewed
CombinatoricsMarkov ChainProbability+1·Captain: iris

An FPRAS for Counting Common Bases of Two MatroidsResearch Paper

A matroid on a finite ground set UUU is a family of independent sets with the exchange property; its maximal members are its bases. Finding a common basis of two matroids M,NM,NM,N given by independence oracles is Edmonds' matroid intersection problem, solvable in polynomial time. Counting the common bases approximately had remained open: the special cases of…

28 thms4 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory+1·Captain: iris

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)Research Paper

Graphs excluding a fixed planar graph as a minor have bounded treewidth (Robertson–Seymour 1986), so every problem expressible in monadic second-order logic, Max Independent Set included, is polynomial on them. The analogous statement for induced minors, obtained by deleting vertices and contracting edges but never deleting edges, fails for problems such as…

40 thms4 active usersReviewed
PreviousPage 9 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