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.

1360 open missions

Missions

601–625 of 1360
Open1360Completed139All1499
AlgebraComplexity Theory·Captain: Shuze Chen

A Dichotomy for Complex Boolean Holant with Binary DisequalityResearch Paper

Many counting problems ask for a sum, over all assignments of bits, of a product of local weights. A complexity dichotomy sorts every choice of local weights into two classes: those for which the sum can be computed in polynomial time, and those for which computing it is #P-hard. For Boolean counting constraint satisfaction such dichotomies are known for…

30 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array IndexesResearch Paper

The suffix array SAT\mathrm{SA}_TSAT​ of a text T∈[0..σ)nT \in [0..\sigma)^nT∈[0..σ)n lists the starting positions of the suffixes of TTT in lexicographic order. Its inverse, the inverse suffix array SAT−1\mathrm{SA}^{-1}_TSAT−1​, maps a position jjj to the lexicographic rank of the suffix T[j..n]T[j..n]T[j..n]. Both arrays are central to text indexing, data compression and string algorithms. Stored…

20 thms2 active usersReviewed
CombinatoricsFunctional AnalysisRandom Matrix Theory+1·Captain: Shuze Chen

A Walk from Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer ProblemResearch Paper

Let v1,…,vn∈Cmv_1,\dots,v_n\in\mathbb C^mv1​,…,vn​∈Cm satisfy ∑ivivi∗=Im\sum_i v_iv_i^*=I_m∑i​vi​vi∗​=Im​ and ∥vi∥2≤ε\|v_i\|^2\le\varepsilon∥vi​∥2≤ε for every iii. Weaver's discrepancy problem asks for signs σ∈{−1,1}n\sigma\in\{-1,1\}^nσ∈{−1,1}n for which the operator norm ∥∑iσivivi∗∥\|\sum_i\sigma_iv_iv_i^*\|∥∑i​σi​vi​vi∗​∥ is small, equivalently a partition of the vectors into two sets whose frame operators are both close to Im/2I_m/2Im​/2. Weaver (Wea04) showed that a…

22 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability+1·Captain: Shuze Chen

Faster Equal-Subset-Sum via Truncated Inclusion–ExclusionResearch Paper

Equal-Subset-Sum asks, given integers x1,…,xnx_1,\dots,x_nx1​,…,xn​, for two distinct index sets S,T⊆{1,…,n}S,T\subseteq\{1,\dots,n\}S,T⊆{1,…,n} with ∑i∈Sxi=∑i∈Txi\sum_{i\in S}x_i=\sum_{i\in T}x_i∑i∈S​xi​=∑i∈T​xi​. It sits beside Subset-Sum and Partition among the basic NP-hard number problems, but it has no target sum: the algorithm must find both the sets and their common value. Its worst-case exponential running time has…

19 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Understanding Model Misspecification in Low-Rank Distributions: Tolerant Testing and Agnostic LearningResearch Paper

Sequence models such as hidden Markov models, tensor trains and autoregressive language models define laws on strings of length TTT over a finite alphabet. A common measure of their complexity is the distribution rank: the largest rank of the matrices that pair every history with every future. Low-rank laws can be learned efficiently from conditional samples…

20 thms2 active usersReviewed
cryptographyLinear algebraProbability+1·Captain: Shuze Chen

Leakage-Resilient Computation via Matrix RefreshingResearch Paper

Physical implementations of cryptography leak: power consumption, timing and electromagnetic emanations reveal functions of the secret state. Leakage-resilient cryptography asks for storage and computation that stay secure when an adversary repeatedly learns bounded functions of the internal state. In the split-state (or only computation leaks) model the…

21 thms2 active usersReviewed
CombinatoricsMachine LearningProbability+1·Captain: Shuze Chen

The Margin Complexity of Maxima of Linear FunctionalsResearch Paper

The maximum of rrr linear functionals, x↦max⁡j≤r⟨uj,x⟩x\mapsto\max_{j\le r}\langle u_j,x\ranglex↦maxj≤r​⟨uj​,x⟩, is the simplest non-linear aggregation in learning theory. It describes polyhedral classifiers, one-hidden-layer networks with max pooling, the loss class of kkk-means, and multi-vector retrieval models that keep several embedding vectors per item. Its statistical complexity at a…

25 thms2 active usersReviewed
Complexity TheorycryptographyInformation Theory+1·Captain: Shuze Chen

Quadratic Statistical Randomized Encoding for All FunctionsResearch Paper

A randomized encoding of a function fff replaces fff by a randomized function f^(v;r)\hat f(v;r)f^​(v;r) whose output reveals f(v)f(v)f(v) and nothing else about vvv. Encodings are useful when f^\hat ff^​ is much simpler to compute than fff. They underlie parallel cryptography (one-way functions, pseudorandom generators and encryption computable in constant output locality), and they are the…

29 thms2 active usersReviewed
CombinatoricsComputational ComplexityLogic+1·Captain: Shuze Chen

Polynomial Interpolation for Sherali-Adams Lower BoundsResearch Paper

Sherali-Adams is the standard proof system for refuting unsatisfiable CNF formulas with linear programming. Its refutations are linear-programming certificates over products of literals, the same objects that underlie the Sherali-Adams hierarchy of LP relaxations (Sherali–Adams 1990). It polynomially simulates Resolution, the proof system whose lines are…

23 thms2 active usersReviewed
Computational ComplexityGroup TheoryTheoretical Computer Science·Captain: Shuze Chen

Word Length and Diameter in Permutation GroupsResearch Paper

A finite group GGG generated by a set Σ\SigmaΣ raises a basic quantitative question: how many generators must be multiplied to reach a given element? The answer is measured by the length ℓ(g,Σ)\ell(g,\Sigma)ℓ(g,Σ) of an element and the diameter diam⁡(G,Σ)\operatorname{diam}(G,\Sigma)diam(G,Σ) of the group. Geometrically they are distances in the directed Cayley graph of GGG, and they appear in…

25 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: Shuze Chen

Optimal (Randomized) Compact Routing SchemesResearch Paper

A routing scheme delivers messages in a network in which every vertex forwards a message using only the information it stores. Storing a full shortest-path table at every vertex costs Θ(n)\Theta(n)Θ(n) words per vertex, which is too much for large networks, so compact routing trades storage for longer routes. The trade-off has been studied since the late 1980s:…

21 thms2 active usersReviewed
Computational ComplexityMathematical Logic·Captain: mikedeng1

Approximate Counting and the Provability of Combinatorial PrinciplesResearch Paper

Randomized algorithm analysis repeatedly estimates the fraction of inputs accepted by a Boolean computation. A formal theory of approximate counting specifies which assertions about those estimates can be used in a proof. Its strength matters when comparing probabilistic reasoning with combinatorial principles. Korten, Li, Oliveira and Ren study this…

17 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Sublinear-Time Algorithms on Massive Data StreamsResearch Paper

Graph property testing asks how much of a graph must be inspected to distinguish a property from a substantial violation. A query may be expensive even when storing previous answers is cheap. This motivates streaming testing: vertices pass once through an interface, and an algorithm chooses which arriving vertices to inspect. The question is whether answers…

31 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Accepting Subcubes and the Approximability of Complete Boolean Min-CSPsResearch Paper

In a minimum constraint satisfaction problem (Min-CSP) the input is a set of Boolean variables and a list of constraints, and the goal is an assignment violating as few constraints as possible. On general instances, Min-2-CNF Deletion has an O(log⁡n)O(\sqrt{\log n})O(logn​)-approximation, while a constant factor would refute the Unique Games Conjecture; for Min-3-SAT any…

40 thms2 active usersReviewed
AlgebraComputational ComplexityTheoretical Computer Science·Captain: iris

A Circuit Complexity Trichotomy For Regular LanguagesResearch Paper

Unbounded fan-in Boolean circuits are the standard model of parallel computation, and finite automata the standard model of sequential computation with constant memory. Regular languages sit where the two meet: they separate AC0\mathsf{AC}^0AC0 from NC1\mathsf{NC}^1NC1 (Furst, Saxe, Sipser 1984), any separation of ACC0\mathsf{ACC}^0ACC0 or TC0\mathsf{TC}^0TC0 from NC1\mathsf{NC}^1NC1 is…

51 thms2 active usersReviewed
CombinatoricsConvex OptimizationProbability+1·Captain: Shuze Chen

Subexponential Approximation of the Permanent in Deterministic Polynomial TimeResearch Paper

The permanent of an n×nn\times nn×n matrix AAA is

23 thms2 active usersReviewed
Algebraic GeometryComplexity TheoryComputational Complexity·Captain: iris

Some algebraic and geometric computations in CH via Chow formsResearch Paper

Decomposing an algebraic variety into equidimensional components is a basic task of computer algebra: most algorithms for irreducible decomposition first split a variety by dimension and then factor each piece. Andrews, Garg, Oliveira and Schost (arXiv:2611.05289) place several problems about equidimensional components in the counting hierarchy CH, where…

38 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and SpannersResearch Paper

A directed network can have very different distances in its two directions. A compact family of trees is useful when paths must be represented using edges of the original network, while limiting the number of structures that store each vertex. Distance oracles, spanners and routing schemes use such representations. The structural result considered here…

16 thms2 active usersReviewed
Functional AnalysisQuantum InformationRandom Matrix Theory+1·Captain: mikedeng1

Quantum Advantage for Distributed Symmetry BreakingResearch Paper

In distributed computing, symmetry breaking asks the nodes of a network, all running the same program, to produce locally different outputs; the basic example is a proper colouring of a cycle. In the classical LOCAL model, 3-colouring an nnn-cycle requires Θ(log⁡∗n)\Theta(\log^* n)Θ(log∗n) communication rounds, with or without randomness (Linial 1992). Whether quantum…

30 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

Beyond IP= PSPACE and QIP= PSPACE: Interactive Proofs in Arbitrary Physical TheoriesResearch Paper

An interactive proof lets a verifier with bounded computational power check a claim by exchanging messages with an all-powerful prover. Two theorems describe the power of the model: classical interactive proofs decide exactly polynomial space, IP=PSPACE\mathsf{IP}=\mathsf{PSPACE}IP=PSPACE (Lund, Fortnow, Karloff and Nisan; Shamir; Shen, 1990–92), and quantum interactive…

26 thms2 active usersReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

The Power and Limits of Money Burning in Bilateral TradeResearch Paper

In bilateral trade a seller owns one indivisible good and a buyer may want it. Each trader privately knows their own value. A mechanism asks both for reports and decides whether to trade and what each trader pays or receives. A mechanism is strongly budget-balanced (SBB) when the buyer's payment always equals the seller's receipt. It is weakly…

38 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

A Near-Optimal Parallel Algorithm for Finding Matroid BasesResearch Paper

A matroid M=(E,I)M=(E,\mathcal I)M=(E,I) on a finite ground set EEE of nnn elements is a family I\mathcal II of independent sets that contains ∅\emptyset∅, is closed under taking subsets, and satisfies the exchange property. Spanning forests of graphs and bases of vector configurations are the standard examples. A basis is a maximal independent set. Because the number of…

27 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Finding and Certifying Weighted Minimum Cuts with Cut QueriesResearch Paper

A cut query asks for the total capacity joining a specified set of vertices to its complement. It provides an aggregate measurement of an unknown graph rather than a list of its edges. Researchers studying graph query complexity ask how many such measurements suffice to determine an optimization value. For minimum cut, a related question concerns…

23 thms2 active usersReviewed
Algorithmic Game TheoryAnalysis·Captain: mikedeng1

Tight Bounds on the Menu-Size Complexity of Approximately Optimal Auctions with Two ItemsResearch Paper

A seller offering two items to one buyer can offer lotteries as well as deterministic purchases. Describing a lottery requires two allocation probabilities and a price, and an auction may offer many such alternatives. Menu size measures how many distinct nonnull alternatives are required. The resulting question concerns the complexity of implementing a…

21 thms2 active usersReviewed
Computational ComplexityGraph TheoryQuantum Information·Captain: mikedeng1

A Quantum Lower Bound for Triangle FindingResearch Paper

A triangle is a set of three distinct vertices joined by all three possible edges. In the adjacency-matrix query model, a graph is hidden and an algorithm learns whether two vertices are adjacent by querying their pair. Triangle finding asks the algorithm to return a triangle whenever one exists. The resource being measured is the number of queries;…

20 thms2 active usersReviewed
PreviousPage 25 of 55Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn690113
3SHshivm1630
4PAparclytaxel150172
5MTmartelus trismortuus1050
6GAgaryholm900
7WCwcysai8486
8A1a142857a7518
9SCSenrui Chen6757
10BEbersubs6574

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