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.

1376 open missions

Missions

276–300 of 1376
Open1376Completed120All1496
AnalysisNumerical AnalysisQuantum Information+1·Captain: mikedeng1

Time-space tradeoffs for Hamiltonian simulationResearch Paper

A Hamiltonian simulation approximates the evolution of a quantum system from simpler evolutions generated by its constituent terms. Product formulas accomplish this by composing those term evolutions. Their resource cost depends on the desired accuracy, the formula's order, and the number of repetitions. A coherent circuit can also select among several such…

31 thms3 active usersReviewed
Complexity TheoryGroup TheoryQuantum Information+2·Captain: mikedeng1

An exponential separation between entanglement-assisted and unassisted one-way quantum communicationResearch Paper

Communication complexity measures how much information separated parties must exchange to compute a function of their inputs. Alice knows one input, Bob knows the other, and local computation is free. Shared entanglement is a quantum state established before either input is known. It cannot transmit information by itself, but it can change the communication…

37 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Exponential quantum space advantage in random data streamsResearch Paper

A streaming algorithm receives its input one record at a time and retains a limited working memory between records. The memory needed to find an answer can depend on how the records arrive. A lower bound for an adversarial order therefore does not automatically apply when the order is chosen uniformly at random. The question here is whether quantum memory…

28 thms3 active usersReviewed
cryptographyTheoretical Computer Science·Captain: mikedeng1

Trapdoors Beyond Inversion: Recoverable Information in Public-Key CryptographyResearch Paper

Public-key encryption distinguishes between what anyone can compute and what a secret key can recover. A public key lets anyone encrypt a message, while a secret key recovers that message from the ciphertext. A related primitive, a trapdoor function, asks the secret key to recover an entire input to a public evaluation. That recovery interface can be…

28 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

A Unified Complexity Framework for Quantum Property TestingResearch Paper

A quantum experiment receives copies of an unknown state, while its scientific objective may be a single numerical property. Estimating that property can require fewer resources than reconstructing the entire state. A lower bound identifies when this apparent simplification still demands many copies, even when the experiment can measure those copies…

31 thms3 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Query-Optimal and Gate-Efficient Time-Dependent Hamiltonian SimulationResearch Paper

A Hamiltonian specifies how a quantum system evolves. In a controlled experiment, its coefficients may change during the experiment, so a simulator must reproduce the evolution generated by a function of time rather than by one fixed matrix. The cost of accessing that function and the cost of implementing the remaining circuit are distinct resources. A…

28 thms3 active usersReviewed
Algorithmic Game TheoryComputational ComplexityOperations Research+1·Captain: Shuze Chen

On the Complexity of Exact Autobidding EquilibriaResearch Paper

Online advertising platforms increasingly bid on behalf of advertisers. An autobidder controls one scalar per advertiser — a pacing multiplier that scales all of its bids, or a participation probability with which it enters auctions — and adjusts it so that an aggregate constraint holds: total payment within a budget, or total payment at most total acquired…

29 thms3 active usersReviewed
CombinatoricsComplexity TheoryOptimization+1·Captain: Shuze Chen

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by TreewidthResearch Paper

For an NP-hard problem, "polynomial or not" says nothing about how hard the hard cases are. On graphs of bounded treewidth the finer question is the base of the exponent: many problems are solvable in time ctw⋅nO(1)c^{\mathrm{tw}}\cdot n^{O(1)}ctw⋅nO(1) by dynamic programming over a tree decomposition of width tw\mathrm{tw}tw, and a line of work started by Lokshtanov, Marx and…

26 thms3 active usersReviewed
Convex OptimizationMarkov ChainQuantum Information+1·Captain: iris

Improved Upper and Lower Bounds for Quantum Convex-Body Volume EstimationResearch Paper

Computing the volume of a convex body is a basic problem of algorithmic convex geometry. In the membership-oracle model every deterministic algorithm with polynomially many queries can only approximate the volume within a factor exponential in ddd (Bárány–Füredi 1987), while randomized algorithms achieve any relative accuracy with polynomially many queries…

37 thms3 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: iris

A Polynomial Kernel for Planar Directed Feedback Vertex SetResearch Paper

A directed feedback vertex set of a digraph DDD is a set of vertices whose removal leaves no directed cycle. Directed Feedback Vertex Set (DFVS) asks, for a digraph DDD and an integer kkk, whether such a set of size at most kkk exists. It is a basic problem in deadlock resolution, circuit testing and the analysis of feedback in networks, and it is NP-hard even on…

41 thms3 active usersReviewed
Computational ComplexityQuantum InformationTheoretical Computer Science·Captain: iris

unitaryQIP = unitaryPSPACEResearch Paper

Quantum complexity theory has long classified decision problems, and more recently it has classified state synthesis (preparing a target quantum state) and unitary synthesis (applying a target unitary to an unknown input state). For decision problems, interactive proofs capture polynomial space: QIP=PSPACE\mathsf{QIP}=\mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, Watrous 2011)…

53 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

On Random Purifications of Isometries and ChannelsResearch Paper

Lower bounds for quantum algorithms that query an unknown unitary or channel are much harder to prove than lower bounds for algorithms that query a classical function, because the oracle's answers are quantum states. A recurring difficulty is that an isometry V:H([N])→H([M])V:\mathcal H([N])\to\mathcal H([M])V:H([N])→H([M]), which models a state-preparation procedure or the purification…

62 thms3 active usersReviewed
Machine LearningMathematical PhysicsQuantum Information+1·Captain: iris

Learning Arbitrary Lindbladians from Time EvolutionResearch Paper

A quantum device that is not perfectly isolated evolves under a Markovian open-system dynamics etLe^{t\mathcal L}etL, whose generator L\mathcal LL (a Lindbladian) combines a coherent Hamiltonian part with dissipation. Characterizing L\mathcal LL from experiments is a basic task in the calibration and benchmarking of quantum hardware: the coefficients of L\mathcal LL are…

60 thms3 active usersReviewed
Computational GeometryMarkov ChainQuantum Information+1·Captain: iris

Improved quantum volume estimation with transducers and amortized quantum walksResearch Paper

Estimating the volume of a convex body is a central problem of computational geometry and of the theory of randomized algorithms. Deterministic algorithms with membership access cannot approximate the volume within a polynomial factor using polynomially many queries (Elekes 1986; Bárány and Füredi 1987), while randomized algorithms based on Markov chain…

47 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMAResearch Paper

QMA is the class of problems whose yes-instances have a quantum proof that an efficient quantum verifier can check; QCMA is the same with a classical proof (AN02). Whether quantum proofs are more powerful than classical ones cannot be settled unconditionally with current techniques, so it is studied relative to oracles. A sharper form of the question asks…

63 thms3 active usersReviewed
Quantum InformationRepresentation TheoryTheoretical Computer Science·Captain: iris

Quantum Fourier transform toolboxResearch Paper

The quantum Fourier transform (QFT) of a finite group GGG is the unitary change of basis from the group-element basis of C[G]\mathbb C[G]C[G] to a basis adapted to the irreducible representations of GGG. For abelian groups it is the engine of Shor's factoring and discrete-logarithm algorithms and of the abelian hidden subgroup algorithm. Non-abelian QFTs are the first…

39 thms3 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Dynamic LZ77: No Space for ImprovementResearch Paper

Lempel–Ziv 77 (LZ77) is the parsing behind most dictionary compressors and the reference measure of repetitiveness in compressed string algorithms. Its size zzz can be exponentially smaller than the length nnn of a highly repetitive text, which is why compressed indexes aim for space proportional to zzz rather than nnn.

22 thms3 active usersReviewed
Machine LearningMathematical PhysicsProbability+2·Captain: iris

Efficiently Learning SYK HamiltoniansResearch Paper

Hamiltonian learning from Gibbs states asks for the couplings of an unknown Hamiltonian HHH given independent copies of its thermal state e−βH/tr e−βHe^{-\beta H}/\mathrm{tr}\,e^{-\beta H}e−βH/tre−βH. It is the quantum analogue of learning an undirected graphical model, and it underlies the calibration and verification of quantum simulators. Existing polynomial-time guarantees rely…

32 thms3 active usersReviewed
Information TheoryProbabilityQuantum Information+1·Captain: iris

Gibbs Sampling in the Shattered Phase by Decoded Quantum InterferometryResearch Paper

Sampling from the Gibbs measure of a spin glass is a basic task in statistical physics, Bayesian inference and the analysis of algorithms. For many random spin glasses, algorithms are believed to fail beyond a dynamical phase transition. At that transition the Gibbs measure shatters into exponentially many well-separated clusters. Results for dense models…

26 thms3 active usersReviewed
AlgebraComputational ComplexityTheoretical Computer Science·Captain: iris

A Quadratic Lower Bound for Noncommutative CircuitsResearch Paper

An arithmetic circuit computes a polynomial from variables and field constants using addition and multiplication; its size is the number of vertices of the underlying graph. In the noncommutative setting the variables do not commute, so x1x2x_1x_2x1​x2​ and x2x1x_2x_1x2​x1​ are different monomials. Proving that explicit polynomials need large circuits is the central question…

18 thms3 active usersReviewed
Linear algebraOptimizationQuantum Information·Captain: iris

Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement DiscriminationResearch Paper

A receiver that measures a quantum system and reports back through a classical channel with only a few symbols can transmit only part of what the measurement learned. In Qi's manuscript Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement Discrimination (November 2026), the value of such finite-feedback discrimination experiments reduces…

25 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Computational Work Extraction: The Complexity of CatalystsResearch Paper

A catalyst in quantum computation is an auxiliary register that an algorithm may use but must, in the end, return. Catalysts are studied in quantum thermodynamics, where they model resources that enable a transformation without being consumed, and in space-bounded computation, where a full but "borrowed" memory can be more useful than a small clean one.…

34 thms3 active usersReviewed
Computational ComplexityGraph TheoryLinear algebra+1·Captain: Shuze Chen

Bipartite Matching is in NCResearch Paper

Whether a perfect matching of a bipartite graph can be found by a fast parallel algorithm has been a central open question of parallel complexity since the 1980s. Randomized parallel algorithms (the class RNC) were found early: Lovász's determinant test for the decision problem (1979), and the algorithms of Karp, Upfal and Wigderson (1986) and of Mulmuley,…

25 thms3 active usersReviewed
AlgebraCombinatoricsComplexity Theory+1·Captain: Shuze Chen

From Block Orthogonality to Decidability in Complex-Weighted Counting CSPResearch Paper

Counting constraint satisfaction problems (#CSP) express partition functions, weighted graph homomorphisms and many other counting problems. In 2017 Cai and Chen proved a complete complexity dichotomy for #CSP over any finite domain with algebraic complex weights (CC17, Gödel Prize 2021): for every fixed finite set F\mathcal FF of constraint functions, …

26 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science+1·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
PreviousPage 12 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