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

301–325 of 1496
Open1376Completed120All1496
cryptographyDiscrete GeometryProbability+1·Captain: iris

Gaussian Difference Dynamics: Breaking the 2n/22^{n/2}2n/2 Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingResearch Paper

A lattice L=BZnL = B\mathbb Z^nL=BZn is the set of integer combinations of the columns of a nonsingular matrix BBB. The shortest vector problem (SVP) asks for a nonzero vector of LLL of minimal Euclidean length λ1(L)\lambda_1(L)λ1​(L). Exact SVP is the computational core of lattice basis reduction, and its running time calibrates the security estimates of lattice-based…

68 thms3 active usersReviewed
Complexity TheorycryptographyProbability+1·Captain: iris

Faster Provable Algorithm For Random Modular Subset SumResearch Paper

Subset sum asks, given integers a1,…,ana_1,\dots,a_na1​,…,an​ and a target ttt, for a set of indices whose coefficients sum to ttt. Its random modular version, with coefficients uniform in Z/QZ\mathbb Z/Q\mathbb ZZ/QZ and a planted binary solution, is the standard benchmark for generic attacks on knapsack-type cryptosystems and for the representation technique of Howgrave-Graham and…

27 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Separating ClonableQMA and QCMA Relative to a Classical OracleResearch Paper

A quantum proof is a quantum state handed to an efficient verifier. The class QMA allows arbitrary quantum proofs, while QCMA restricts them to classical strings. Whether quantum proofs are ever more powerful than classical ones is open in the unrelativized world, and the question has been studied through oracle separations since Aaronson and Kuperberg (CCC…

27 thms3 active usersReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

Massively Parallel Algorithms for Huffman CodingResearch Paper

Huffman coding assigns binary codewords to the characters of a text so that no codeword is a prefix of another and the encoded text is as short as possible. Huffman's greedy algorithm (Huffman 1952) solves it in linear time once the character frequencies are sorted. It is a basic step of practical compression.

27 thms3 active usersReviewed
Functional AnalysisOptimizationProbability+1·Captain: mikedeng1

Primal/Dual Method for the Grothendieck ConstantResearch Paper

The real Grothendieck constant KGK_GKG​ measures how much a semidefinite relaxation can overestimate a bilinear ±1\pm1±1 optimization problem. It appears in Banach-space theory, where it is the best constant in Grothendieck's inequality Pis12; in quantum information, where it bounds the violation of correlation Bell inequalities AGT06; and in approximation…

24 thms3 active usersReviewed
CombinatoricsMarkov ChainProbability·Captain: mikedeng1

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness ThresholdResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic problem in approximate counting and statistical physics: it is the zero-temperature antiferromagnetic Potts model, and an efficient sampler yields an approximation of the number of colourings. The standard sampler is the single-site Glauber dynamics: pick a uniformly random vertex and…

24 thms3 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Optimal Contention Resolution from SamplesResearch Paper

A contention resolution scheme receives a random collection of available elements and selects a feasible subset. With a capacity of kkk, feasibility means selecting at most kkk elements. The input can respect capacity on average while exceeding it on particular realizations. A useful selection rule must resolve these conflicts while preserving a guarantee for…

40 thms3 active usersReviewed
Complexity TheoryInformation Theory·Captain: mikedeng1

Efficient Randomized Communication Without Large Monochromatic RectanglesResearch Paper

In Yao's two-party model, Alice holds x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, Bob holds y∈{0,1}ny\in\{0,1\}^ny∈{0,1}n, and they exchange bits to compute a Boolean function F(x,y)F(x,y)F(x,y). The randomized communication complexity R(F)R(F)R(F) is the least worst-case number of bits of a public-coin protocol that errs with probability at most 1/31/31/3 on every input. Two questions about total functions motivate this…

22 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal ConstructionsResearch Paper

Averaging samplers estimate the mean of a bounded function on {0,1}m\{0,1\}^m{0,1}m from a few correlated sample points generated by a short random string. Randomness extractors turn a weakly random source plus a short uniform seed into nearly uniform bits. Zuckerman showed that the two objects are the same thing seen from two sides: enumerating all seeds of an…

12 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsComplexity Theory+1·Captain: mikedeng1

Learning and Optimisation of Rank Ordered Gain Functions and with Modular CostsResearch Paper

A principal choosing a group of workers must compare the group's collective value with the cost of engaging its members. Individual competencies give useful ordering information, but a ranking alone does not describe how participation costs interact with collective performance. Etesami, Liu and Sahitaj study this distinction through augmented rank-ordered…

26 thms3 active usersReviewed
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
PreviousPage 13 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