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.

1499 missions

Missions

101–125 of 1499
Open1321Completed178All1499
Complexity TheoryConvex OptimizationTheoretical Computer Science·Captain: iris

Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order QueriesResearch Paper

Classical oracle complexity counts how many exact first-order answers — a value f(y)f(y)f(y) and a subgradient g∈∂f(y)g\in\partial f(y)g∈∂f(y) — a method needs to minimize a convex function. With exact real answers, O(dlog⁡(MR/ε))O(d\log(MR/\varepsilon))O(dlog(MR/ε)) queries suffice in dimension ddd, attained by the center of gravity method and by modern cutting-plane methods. A computer, however, reads…

62 thms5 active usersReviewed
CombinatoricsComplexity TheoryOperations Research·Captain: iris

Additive Ω(log⁡∗OPT)\Omega(\log^* OPT)Ω(log∗OPT) Gap for Bin Packing with Three Items per BinResearch Paper

In bin packing, items with sizes in (0,1](0,1](0,1] must be partitioned into bins of total size at most one, using as few bins as possible; OPT(I)\mathrm{OPT}(I)OPT(I) is that minimum. The problem is strongly NP-hard even in the 3-partition regime, where every size lies in (1/4,1/2)(1/4,1/2)(1/4,1/2) and a bin holds at most three items, so research has concentrated on additive guarantees …

28 thms5 active usersReviewed
Bandit AlgorithmsGraph TheoryMachine Learning·Captain: iris

The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback GraphsResearch Paper

Online learning algorithms randomize to hedge against an adversary, and independent resampling makes them change action often. When changing a route, a deployed model or a treatment has a cost of its own, the right benchmark charges one unit per change. With full information this charge leaves the minimax regret at order Tlog⁡K\sqrt{T\log K}TlogK​ (Kalai and Vempala,…

40 thms5 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory·Captain: iris

0/10/10/1-Polytopes with Exponentially Small Edge ExpansionResearch Paper

A 0/1-polytope in Rd\mathbb R^dRd is the convex hull of a nonempty set of vertices of the Boolean cube {0,1}d\{0,1\}^d{0,1}d. Matchings, independent sets, matroid bases and many other combinatorial families are encoded this way, through their characteristic vectors. The graph G(P)G(P)G(P) of such a polytope (its vertices and edges) is the state space of natural random walks, and…

27 thms5 active usersReviewed
🏆Completed
Graph TheoryNumber TheoryQuantum Information·Captain: iris

Structural Accessibility in Phase-Encoded Quantum Graph EmbeddingsResearch Paper

A phase-encoded quantum graph embedding writes a graph GGG on nnn vertices into nnn qubits through a fixed, shallow circuit and reads it out by measuring in the computational basis. Such fixed circuits are proposed as graph features for learning and for graph comparison, and parameterized versions of them (QAOA-type circuits) are studied as quantum graph neural…

30 thms4 active usersReviewed
Information TheoryStatisticsTheoretical Computer Science·Captain: iris

Testing Fairness of Evolving Software under UncertaintyResearch Paper

Fairness testing checks that a program treats comparable inputs comparably, for instance that two inputs differing only in a protected attribute receive the same favourable outcome with nearly the same probability (Galhotra, Brun, Meliou 2017). Deployed software changes: a program P0P_0P0​ that has already been certified is replaced by a patched program P1P_1P1​, and…

42 thms4 active usersReviewed
ProbabilityReinforcement LearningStatistics·Captain: iris

When Can Physical Evidence Survive a World-Model Update? Finite-Cost Re-Auditing and Reusable Policy CertificatesResearch Paper

Learned world models let a controller propose new policies after every update of an encoder, a simulator or a planner, without collecting any new physical data. When the physical dynamics themselves change, old evidence no longer certifies anything about the new environment, and fresh interaction is needed. Fresh interaction is expensive in a specific way:…

25 thms4 active usersReviewed
Machine LearningQuantum Information·Captain: mikedeng1

Agnostic proper learning of stabilizer states from Pauli measurementsResearch Paper

A quantum experiment consumes copies of an unknown state to obtain classical observations. When the observables of interest commute, several outcomes can be obtained from one copy. This matters for predicting outcomes of Pauli measurements and for evaluating sums of Pauli terms in quantum algorithms. A prediction task asks for more than estimating one…

33 thms4 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Deterministic o(mn)o(mn)o(mn)-time algorithms for computing the kkk-connected components in directed graphsResearch Paper

Edge connectivity measures how robust a network is against link failures. In a directed graph, two vertices are kkk-edge-connected when kkk pairwise edge-disjoint directed paths run from each to the other; this relation is an equivalence, and its classes, the kkk-edge-connected components, describe which groups of vertices survive the deletion of any k−1k-1k−1 edges…

108 thms4 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: iris

Classical Verification of Quantum Sampling with Negligible ErrorResearch Paper

A quantum computer that is asked for a sample from the output distribution of a circuit returns a string, and nothing in that string shows whether the circuit was actually run. Classical verification of quantum sampling asks for an interactive protocol in which a fully classical, polynomial-time verifier talks to an untrusted quantum prover and outputs…

35 thms4 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryProbability+1·Captain: Shuze Chen

Dictators are most informativeResearch Paper

How much information about a noisy vector can one bit retain? Let XXX be uniform on {−1,1}n\{-1,1\}^n{−1,1}n and let YρY_\rhoYρ​ be obtained from XXX by flipping each coordinate independently with probability (1−ρ)/2(1-\rho)/2(1−ρ)/2, so that ρ∈[0,1]\rho\in[0,1]ρ∈[0,1] is the correlation. A one-bit summary is f(X)f(X)f(X) for a Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1}, and the question is which fff maximizes the mutua…

22 thms4 active usersReviewed
cryptographyQuantum Information·Captain: mikedeng1

EFI⇔1PRS\mathsf{EFI}\Leftrightarrow\mathsf{1PRS}EFI⇔1PRSResearch Paper

A cryptographic primitive can hide a classical choice, describe apparent randomness, or express the difficulty of recovering a secret key. Establishing that such tasks require the same computational assumption helps identify which assumptions a larger protocol actually needs. This mission concerns two quantum primitives: EFI pairs, which hide a choice…

35 thms4 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Cryptographic Guarantees for Distributed Training Under Malicious AdversariesResearch Paper

Distributed training splits the computation of a gradient across many workers whose contributions are combined by an aggregation server. When some workers are malicious and the server is untrusted, protocols add three kinds of safeguard: cryptographic checks that a reported aggregate is consistent with committed local gradients, differential privacy noise…

9 thms4 active usersReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Quantum Tolerant Testing of Fourier Dimensionality and JuntasResearch Paper

Tolerant property testing asks whether an unknown function, available only through queries, is close to a class of functions or far from it. Standard testing accepts every function in the class and rejects inputs at distance at least a specified threshold. Tolerant testing requires that inputs at distance at most ε1\varepsilon_1ε1​ be accepted and inputs at…

34 thms4 active usersReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Edit-Robust Pseudorandom Codes, Watermarks, and SteganographyResearch Paper

A pseudorandom code (PRC) is a secret-key error-correcting code whose codewords look uniformly random to anyone without the key. It was introduced by Christ and Gunn to build undetectable watermarks for the output of generative models (Christ–Gunn, CRYPTO 2024). A model that samples its tokens with randomness taken from a PRC codeword produces text whose…

12 thms4 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

Faster Dynamic Maximal Independent Set against Adaptive AdversariesResearch Paper

A maximal independent set (MIS) of a graph is a set MMM of vertices, no two adjacent, such that every vertex outside MMM has a neighbour in MMM. It is the basic symmetry-breaking object of parallel and distributed computing. In the fully dynamic setting the graph changes by edge insertions and deletions, and an algorithm must keep an MIS of the current graph…

12 thms4 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory+1·Captain: Shuze Chen

Finding full immersions is fixed-parameter tractable in labeled tour graphsResearch Paper

Testing whether a small graph HHH is contained in a large nnn-vertex graph GGG is a central algorithmic question for every notion of containment. For graph minors the answer has been fixed-parameter tractable since Robertson and Seymour's disjoint-paths algorithm (Graph Minors XIII), and for topological minors and immersions since Grohe, Kawarabayashi, Marx and…

22 thms4 active usersReviewed
Algorithmic Game TheoryCombinatoricsComputational Complexity·Captain: Shuze Chen

Necklace Splitting with Ten Beads per Colour is PPAD-HardResearch Paper

A necklace is a sequence of beads, each of one of nnn colours, where colour ccc occurs 2bc2b_c2bc​ times. Two thieves want to share it fairly: cut it at some positions, hand the pieces out alternately, and each thief must receive exactly bcb_cbc​ beads of every colour. Goldberg–West and Alon–West proved that nnn cuts always suffice, by a topological argument, and the search…

25 thms4 active usersReviewed
Linear algebraProbabilityRandom Matrix Theory+2·Captain: Shuze Chen

Near-Optimal Bounds for Sketching the Schatten NormsResearch Paper

A linear sketch compresses a large object by storing a few linear measurements of it, chosen at random before the object is seen, and answers a query from those measurements alone. Linear sketches are the standard model behind turnstile streaming and distributed aggregation: measurements of a sum are sums of measurements, so updates and merges are free. The…

25 thms4 active usersReviewed
CombinatoricscryptographyHarmonic Analysis+2·Captain: Shuze Chen

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial IntersectionResearch Paper

In Shamir secret sharing over a prime field Fp\mathbb F_pFp​, a secret sss is shared among nnn parties by a uniformly random polynomial PPP of degree at most kkk with P(0)=sP(0)=sP(0)=s; party iii receives P(αi)P(\alpha_i)P(αi​) for distinct nonzero evaluation points αi\alpha_iαi​. Any k+1k+1k+1 parties recover the secret and any kkk learn nothing about it. Local leakage resilience (LLR) asks for more: if…

24 thms4 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

(1+ϵ)(1+\epsilon)(1+ϵ)-Distortion Spanning Tree Covers of Minor-Free Graphs with Size O(log⁡log⁡n)O(\log \log n)O(loglogn)Research Paper

A tree cover of a weighted graph approximates all of its shortest-path distances by a small number of trees: for every pair of vertices, some tree in the collection keeps their distance within a factor α\alphaα, the distortion, and no tree shortens any distance. Tree covers are a standard device for transferring tree algorithms to general graphs, with…

25 thms4 active usersReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Access Cost Tradeoffs in Mixed-Mode Oblivious RAMResearch Paper

An oblivious RAM (ORAM) lets a client keep an array on an untrusted server without revealing which logical addresses it accesses (Goldreich–Ostrovsky 1996). When every access is private, the price is known: with polynomially sublinear client memory, logarithmic overhead is necessary even for computational security (Larsen–Nielsen 2018). Many computations…

19 thms4 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Security of XOR of Permutations via Fourier AnalysisResearch Paper

Block ciphers are modelled as pseudorandom permutations, but many symmetric-key schemes, among them Wegman–Carter MACs and counter mode, are more secure when instantiated with a pseudorandom function. Constructing a pseudorandom function from random permutations (the "Luby–Rackoff backward" problem) is a long-standing line of work. The XOR of permutations an…

41 thms4 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

A classical oracle separation between QMA and QMA(2)Research Paper

QMA is the quantum analogue of NP: a polynomial-time quantum verifier receives a quantum proof (a witness) from an all-powerful prover. QMA(2) is the variant in which the verifier receives two quantum proofs that are promised to be unentangled, i.e. the joint witness is a product state ∣ψ1⟩⊗∣ψ2⟩|\psi_1\rangle\otimes|\psi_2\rangle∣ψ1​⟩⊗∣ψ2​⟩ (KMY03). Whether this promise adds…

32 thms4 active usersReviewed
Computational GeometryConvex OptimizationFunctional Analysis·Captain: mikedeng1

Deterministic Terminal Embedding with Optimal Target Dimension for Euclidean SpaceResearch Paper

A database of points can be reduced to fewer coordinates while approximately preserving distances among its stored points. Many geometric applications also compare those points with centers or queries supplied later. A guarantee only about pairs already in the database does not cover every such comparison. A terminal embedding asks for one map that…

26 thms4 active usersReviewed
PreviousPage 5 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23927601
2DBdbenbenn909166
3SHshivm1630
4PAparclytaxel150172
5LRlreyzin140143
6KMkmehltretter8212219
7MTmartelus trismortuus1050
8BOBoomShaKaLaaaKa93100
9GAgaryholm900
10WCwcysai8486

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