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.

1377 open missions

Missions

151–175 of 1377
Open1377Completed119All1496
Algorithmic Game TheoryOptimizationTheoretical Computer Science·Captain: iris

The Complexity of Continuous Contract Design over PolymatroidsResearch Paper

In a principal–agent problem, a principal delegates work to an agent whose effort is not observed and pays the agent according to the outcome. Linear contracts, which pay the agent a fixed share α\alphaα of the reward, are the simplest and most widely used class; for binary outcomes they are without loss of generality. Algorithmic contract theory asks when…

49 thms4 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Efficient Algorithms for Approximately Counting Bipartite Independent Sets in Low Threshold Rank GraphsResearch Paper

Counting the independent sets of a bipartite graph exactly is #P-hard (Provan and Ball 1983), although a maximum independent set of a bipartite graph is found in polynomial time through a maximum matching. Whether the count can be approximated to relative error in polynomial time is open: for general bipartite graphs neither an FPRAS nor NP-hardness of…

31 thms4 active usersReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: iris

Round-Optimal Statistical Verifiable Secret Sharing with Polynomial ComplexityResearch Paper

Verifiable secret sharing (VSS), introduced by Chor, Goldwasser, Micali and Awerbuch in 1985, lets a dealer distribute a secret among nnn parties so that a coalition of ttt parties learns nothing about it, while every dealer, honest or not, is bound at the end of the sharing phase to one value that the honest parties later reconstruct. Information-theoretic…

16 thms4 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

A Counting and Sampling Lovász Local Lemma IResearch Paper

The Lovász Local Lemma (LLL) gives a sufficient condition for avoiding a family of bad events in terms of their probabilities and their dependencies. In the variable setting there are finitely many independent random variables and a finite family of constraints, each depending on a few of them; the asymmetric LLL guarantees that all constraints can be…

26 thms4 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

Computational Bounds for fff-RoutingResearch Paper

Quantum position verification aims to turn a device's physical location into a verifiable credential, with position-based authentication and key exchange as applications (Buhrman et al. 2014). The central question is whether several colluding devices elsewhere can impersonate a prover at the claimed location. The fff-routing protocol is a leading candidate.…

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

Pure Differentially Private Query Release via Laplace Input SmoothingResearch Paper

Statistical query release asks a curator holding a database of NNN records to publish answers to kkk public counting queries while protecting every individual record. Differential privacy (Dwork, McSherry, Nissim, Smith 2006) is the standard formal guarantee, and its pure form, with no additive slack δ\deltaδ, is the strongest and the easiest to compose. The…

23 thms4 active usersReviewed
Computational ComplexityMathematical PhysicsQuantum Information·Captain: iris

The Complexity of Single-Interaction HamiltoniansResearch Paper

The local Hamiltonian problem asks whether the ground energy of a sum of few-qubit terms lies below a threshold aaa or above a threshold b>ab>ab>a. It is the quantum analogue of constraint satisfaction, and its QMA-completeness (Kitaev, Shen and Vyalyi; for two-local terms Kempe, Kitaev and Regev) is the starting point of Hamiltonian complexity theory. In the…

63 thms4 active usersReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: iris

Add/XNOR Chains: An NP-Complete Boolean–Arithmetic Problem at the Meet-in-the-Middle BarrierResearch Paper

Addition modulo 2m2^m2m and bitwise XOR are the two cheapest operations on machine words, and mixing them is the standard way of destroying algebraic structure: it underlies ARX (add–rotate–XOR) ciphers and most hash functions in use. The paper of Wang, Lv, Shen and Zhang isolates the decision version of this mixing in its simplest form. A chain of words is…

27 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Optimal compression with quantum retrievalResearch Paper

A sparse string x∈{0,1}mx\in\{0,1\}^mx∈{0,1}m with at most nnn ones can be stored in log⁡(mn)≈nlog⁡(m/n)\log\binom{m}{n}\approx n\log(m/n)log(nm​)≈nlog(m/n) bits, far fewer than mmm. The catch is retrieval: a data structure that answers "what is xix_ixi​?" by reading only a few bits of the stored string usually needs much more space. In classical computing this is the static set membership problem in the bit-probe…

16 thms4 active usersReviewed
Graph TheoryMarkov ChainProbability+1·Captain: iris

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness ThresholdResearch Paper

The hardcore model on a graph GGG is the distribution on independent sets III with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣, for a fugacity λ>0\lambda>0λ>0. Its normalizing constant, the partition function ZG(λ)Z_G(\lambda)ZG​(λ), is #P-hard to compute exactly (Valiant, SIAM J. Comput. 1979). On graphs of maximum degree Δ\DeltaΔ, the tree uniqueness threshold …

42 thms4 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: iris

From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive ValuationsResearch Paper

A buyer with budget B>0B>0B>0 wants to buy services from nnn strategic sellers, each holding a private cost, so as to maximize a value function of the set it buys. This is budget-feasible mechanism design, introduced by Singer (2010). It models procurement in data markets, crowdsourcing and content ecosystems, and it departs from the classical setting because VCG…

58 thms4 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: iris

Linear-length cycles in the supercritical percolated hypercubeResearch Paper

The binomial random graph has a well-known phase transition: just above average degree 1, a giant component appears and the longest cycle becomes linear in the number of vertices. Whether the percolated hypercube behaves in the same way has been a recurring question, raised for example in Frieze's 2014 ICM survey. The hypercube is the standard test case for…

27 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryEconomics+1·Captain: iris

Exploring the Tractability Frontier of Hylland–Zeckhauser ModelsResearch Paper

The Hylland–Zeckhauser (HZ) mechanism allocates indivisible goods without money, for instance dormitory rooms to students: each of NNN buyers receives one unit of artificial money and buys probability shares of NNN goods, each available in one copy, and equilibrium prices clear the market. The resulting doubly stochastic allocation is a lottery over assignments…

47 thms4 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum ProofsResearch Paper

In QMA(k)\mathsf{QMA}(k)QMA(k) a polynomial-time quantum verifier receives kkk quantum proofs that are promised to be unentangled with one another. Whether this promise adds power, and how far the completeness–soundness gap of such systems can be amplified, are central open questions in quantum complexity theory (Harrow–Montanaro 2013; Jeronimo–Wu 2023). The usual tool…

51 thms4 active usersReviewed
Algorithmic Game TheoryStatistics·Captain: iris

Robust Forecast Aggregation via Additional QueriesResearch Paper

A principal wants to combine the forecasts of nnn experts into one forecast, with a guarantee that holds without knowing how the experts' information is correlated. This is the robust forecast aggregation problem of Arieli, Babichenko and Smorodinsky (2018). The standard benchmark is pessimistic: Neyman and Roughgarden (2022) show that, even under natural…

65 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryTheoretical Computer Science·Captain: iris

FIXP-Completeness via Reciprocal Gates: Applications to Second-Price AuctionsResearch Paper

Fixed-point theorems guarantee that equilibria exist without saying how to find them. Two-player Nash equilibria have rational solutions of polynomial encoding length, and computing them is PPAD-complete (Chen, Deng, Teng 2009). Games with three or more players may have only irrational equilibria, so exact computation does not fit a discrete class. FIXP,…

33 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

All Unitaries Have Constant Depth Quantum CircuitsResearch Paper

The number of one- and two-qubit gates needed to implement a general nnn-qubit unitary is 2Θ(n)2^{\Theta(n)}2Θ(n): standard synthesis gives the upper bound and counting gives the lower bound. That count leaves open how far the gates can be parallelized when ancilla qubits are free. Classically, unbounded fan-in and fan-out compress any Boolean function to three layers.…

40 thms4 active usersReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: iris

Efficient Robust Learning at the Information-Theoretic LimitResearch Paper

In bounded contamination, the model of Bshouty, Eiron and Kushilevitz (Theoretical Computer Science 2002), an adversary may replace an η\etaη-fraction of a training set arbitrarily, in features and labels alike. Running empirical risk minimization on the corrupted data gives error 2η+ε2\eta+\varepsilon2η+ε, and no deterministic hypothesis does better. Whether a…

44 thms4 active usersReviewed
Computational ComplexityMachine LearningQuantum Information·Captain: iris

Fast Quantum Algorithms for Learning Linear Threshold FunctionsResearch Paper

A linear threshold function (LTF), or halfspace, labels each point of Rn\mathbb R^nRn by the side of a hyperplane on which it lies. LTFs are the classifiers of the perceptron and of linear support vector machines, and learning them is one of the oldest problems in computational learning theory.

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

Pretty good shadow tomographyResearch Paper

Measuring a quantum state disturbs it, so a measurement that reveals one observable can destroy information about another. Shadow tomography, posed by Aaronson, asks what this costs when many copies are available: given copies of an unknown state ρ\rhoρ and observables O1,…,OmO_1,\dots,O_mO1​,…,Om​, estimate every tr⁡(Oiρ)\operatorname{tr}(O_i\rho)tr(Oi​ρ) to within ±ε\pm\varepsilon±ε, with…

36 thms4 active usersReviewed
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
PreviousPage 7 of 56Next

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