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

76–100 of 1496
Open1378Completed118All1496
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small kResearch Paper

In Max-kkk-Cut one is given a graph with non-negative edge weights and must colour its vertices with kkk colours so as to maximise the total weight of the edges whose endpoints receive different colours. For k=2k = 2k=2 this is Max-Cut. For k≥3k \ge 3k≥3 the best polynomial-time algorithms round the semidefinite relaxation of Frieze and Jerrum (Algorithmica 1997); for k=3k = 3k=3…

54 thms5 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

On the pseudorandomness of simple quantum processesResearch Paper

A pseudorandom unitary ensemble is one that no efficient quantum algorithm can tell apart from the Haar measure. Such ensembles underlie quantum cryptography and are used as models of chaotic many-body dynamics. A weaker, purely statistical property is being an approximate unitary ttt-design: the ensemble reproduces the first ttt moments of the Haar measure.…

47 thms5 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

An O(loglogn) Upper Bound on the Price of Stability for Undirected Multicast Shapley GamesResearch Paper

In a network design game each user must connect a source to a destination in a shared network, and the cost of every link that is built is split among the users who route through it. A central planner would pick the routing of least total cost; the users instead pick routes that minimize their own payment, and the two goals can disagree. The price of…

31 thms5 active usersReviewed
Convex OptimizationLinear algebraOptimization+1·Captain: iris

A Fast Lewis-weight Interior-Point Method for Linear Optimization over Product Convex SetsResearch Paper

Many problems in statistics, control and data science minimize a linear objective over a product of small convex sets subject to a few linear equations: ℓp\ell_pℓp​ regression, entropy-regularized transport, and second-order cone programs with small cones. When the number of variables nnn is much larger than the number of equations ddd, the running time in terms of ddd…

27 thms5 active usersReviewed
Complexity TheoryOperations ResearchProbability·Captain: iris

Impatience Makes Matching NP-HardResearch Paper

Ride-hailing platforms, online labour marketplaces, organ-allocation systems and quantum switches all match two sides of a market whose agents do not wait forever. The standard abstraction is a bipartite queueing system: agents of finitely many types arrive over time, the platform decides which compatible pairs to match, and an unmatched agent leaves when…

32 thms5 active usersReviewed
Complexity TheoryGraph TheoryOperations Research+1·Captain: iris

Approximation and Hardness for the Data Validation ProblemResearch Paper

Precedence-constrained scheduling takes a partial order on tasks as input, yet in practice the order is rarely known with full confidence. In product design, assembly, project scheduling and construction, the relation between two tasks is often not documented, and an expert must be consulted to determine it. For automotive assembly, probing direct…

36 thms5 active usersReviewed
Convex OptimizationLinear algebraOptimization+1·Captain: iris

Adaptive Matrix Sparsification with Applications to Empirical Risk Minimization and Computational GeometryResearch Paper

Empirical risk minimization (ERM) is a convex optimization problem that covers linear and ℓp\ell_pℓp​ regression, LASSO, logistic regression, support vector machines and quantile regression. Its dual form is

28 thms5 active usersReviewed
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
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Learning to Think from Multiple Thinkers: How Chain-of-Thought Heterogeneity Affects Efficient LearnabilityResearch Paper

Language models are trained to imitate chains of thought (CoTs), the intermediate tokens a reasoner writes before its answer. A learning-theoretic framework for this was introduced by Joshi, Vardi, Block, Goel, Li, Misiakiewicz and Srebro (COLT 2025, PMLR pp. 3161–3212, cited as [JVB+25] in the paper). In that framework, CoTs generated by a single…

31 thms4 active usersReviewed
Machine LearningOperations ResearchReinforcement Learning·Captain: iris

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive PoliciesResearch Paper

Adaptive policies — recommendation systems, dynamic pricing rules, treatment protocols, trading strategies — choose actions based on the state they observe. A natural audit question is how much of a policy's performance comes from that adaptivity, as opposed to the average mix of actions it plays. Answering it requires a benchmark that plays the same…

20 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
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
PreviousPage 4 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