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

176–200 of 1496
Open1377Completed119All1496
Algorithmic Game TheoryComplexity TheoryMechanism Design·Captain: mikedeng1

On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated PriorsResearch Paper

A first-price auction awards a single item to a highest bidder and charges that bidder her own bid. Choosing a bid therefore involves predicting competitors' behavior. Researchers studying auction computation ask whether an equilibrium can be found efficiently from the publicly available description of bidders' information. The setting here allows their…

31 thms4 active usersReviewed
Quantum Information·Captain: mikedeng1

Distributed Quantum Certification with Clifford EncodersResearch Paper

A laboratory may need to verify that a device prepares a prescribed quantum state without learning a complete description of its output. Quantum state certification makes this a binary decision: accept the prescribed state and reject states separated from it by a specified distance. When independent copies are held in separate laboratories, communication…

29 thms4 active usersReviewed
🏆Completed
Algebraic GeometryComplexity TheoryLinear algebra·Captain: mikedeng1

A Quadratic Lower Bound on Determinantal ComplexityResearch Paper

Determinantal representations are a basic model of algebraic computation. Valiant showed that every polynomial has one and made the size of the smallest such representation central to algebraic complexity, where proving a superpolynomial bound for the permanent is the algebraic analogue of P versus NP (Valiant 1979). Even super-linear bounds in the number…

20 thms4 active usersReviewed
Discrete GeometryNumber TheoryTheoretical Computer Science·Captain: iris

Exact SVP and CVP in Structured Lattices: Polynomial-Space Algorithms and ReductionsResearch Paper

The shortest vector problem (SVP) asks for a shortest nonzero vector of a lattice, and the closest vector problem (CVP) for a lattice vector nearest to a target. For general NNN-dimensional lattices the known 2O(N)2^{O(N)}2O(N)-time algorithms use exponential space (AKS01, MV13, ADRS15), while the fastest polynomial-space algorithms, enumeration in the line of Kannan…

40 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Quantum channel tomography: optimal bounds in the near-boundary regimeResearch Paper

Quantum channel tomography (also called quantum process tomography) asks for a full classical description of an unknown quantum channel, given black-box access to it. It is the standard way to certify gates and devices, and its query complexity is the basic sample-complexity question for learning quantum dynamics.

30 thms4 active usersReviewed
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
PreviousPage 8 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