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.

1347 open missions

Missions

1151–1175 of 1347
Open1347Completed152All1499
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A Tight Ω~(m)\widetilde\Omega (\sqrt m)Ω(m​) Information-theoretic Lower Bound for Randomized Online Set CoverResearch Paper

Online set cover asks how many sets must be purchased when the elements requiring coverage arrive one at a time. It is relevant to the analysis of algorithms that make irrevocable covering decisions before learning which demands will occur. Knowing the available sets does not reveal the future demands. The mathematical question is how much this missing…

13 thms1 active userReviewed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Multi-Party Error Resilience beyond 1n\frac{1}{n}n1​Research Paper

An information dissemination task asks every participant in a communication network to learn every participant's input. This is a useful benchmark for adversarial communication: once a participant knows the full input vector, it can evaluate any specified function of those inputs locally. The distinction between learning all inputs and learning only the…

26 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Small classes have linear neighbourhood complexityResearch Paper

A graph class can be studied by counting how many of its graphs exist on a fixed set of labels. It can also be studied by counting the different adjacency patterns visible on a chosen vertex set inside one graph. These are different measurements: the first concerns a collection of whole graphs, while the second concerns local observations within an…

21 thms1 active userReviewed
Computational ComplexitycryptographyMathematical Logic+1·Captain: Shuze Chen

Fine-Grained Proof Complexity for Elementary Arithmetic in Extended FregeResearch Paper

Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…

18 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Byzantine Partition Detection Under ChurnResearch Paper

Byzantine fault-tolerant protocols are proved correct under two separate assumptions: a bound ttt on the number of faulty processes, and enough vertex connectivity in the communication network (classically, connectivity above a multiple of ttt). The second assumption is usually taken for granted. Sengupta and Perrin ask whether the participants themselves can…

25 thms1 active userReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: Shuze Chen

Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and ErasuresResearch Paper

Secure multi-party computation lets parties compute a joint function of private inputs while revealing nothing beyond the output. In the client–server setting, a few clients with inputs delegate the work to nnn servers that have no inputs, and an adversary may corrupt one client and a fraction α\alphaα of the servers. Oblivious transfer (OT) is the basic…

24 thms1 active userReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: iris

Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNPResearch Paper

A one-way function is an efficiently computable function f:{0,1}n→{0,1}mf : \{0,1\}^n \to \{0,1\}^mf:{0,1}n→{0,1}m that no efficient algorithm can invert on a random image: given y=f(x)y = f(x)y=f(x) for uniform xxx, it is hard to find any x′x'x′ with f(x′)=yf(x') = yf(x′)=y. One-way functions are the minimal assumption of private-key cryptography, and their quantitative strength, the best inversion probability an…

65 thms1 active userReviewed
Algorithmic Game TheoryGraph TheoryMechanism Design+1·Captain: iris

Pairwise Exchanges of Freely Replicable Goods with Negative ExternalitiesResearch Paper

Datasets, software and patents are freely replicable: giving a copy costs the giver nothing directly. Firms that hold such goods are often competitors, so each one gains from acquiring a good and loses when a rival acquires one. Data consortia and patent pools face this tension: every member wants access to the others' goods, and no member wants its rivals…

30 thms1 active userReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

A Fast Algorithm for Subspace ConvolutionResearch Paper

Subset summation asks, given a value f(A)f(A)f(A) for every subset A⊆[n]A\subseteq[n]A⊆[n], for all sums (Zf)(B)=∑A⊆Bf(A)(Zf)(B)=\sum_{A\subseteq B}f(A)(Zf)(B)=∑A⊆B​f(A). The fast zeta transform does this in O(n2n)O(n2^n)O(n2n) additions, and with its inverse, the Möbius transform, it underlies the fastest known algorithms for chromatic number, Hamiltonian path and covering products (Björklund–Husfeldt–Koivisto 2009; Bj…

33 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Initialization with Exponentially Fewer BitsResearch Paper

Wireless sensor networks and ad hoc radio networks often consist of mass-produced devices that start out indistinguishable: they carry no identifiers, run identical code, and share one radio channel. Many distributed algorithms assume that nodes have distinct IDs. So a basic first task is initialization: the nnn nodes must give themselves the distinct IDs …

12 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

An approximate cactus-decomposition for vertex-connectivityResearch Paper

The cactus theorem of Dinitz, Karzanov and Lomonosov (1976) states that the minimum edge-cuts of a connected graph are represented by a cactus: a connected graph in which any two cycles share at most one vertex. That representation underlies algorithms for enumerating minimum cuts, connectivity augmentation and dynamic minimum cuts. For vertex-connectivity…

21 thms1 active userReviewed
Linear algebraTheoretical Computer Science·Captain: Shuze Chen

An Algebraic Semantic Framework for Nondeterministic ComputationResearch Paper

Zheng, Zheng, Wang and Huang, in An Algebraic Semantic Framework for Nondeterministic Computation (July 2026, a STOC 2027 submission), propose to study nondeterminism through algebraic structure attached to tape symbols: two nondeterministic branches are regarded as genuinely independent when the algebraic numbers that encode them are linearly independent…

9 thms1 active userReviewed
AlgebraComputational ComplexityTheoretical Computer Science·Captain: iris

Demystifying Border of Structured Algebraic Circuits via Differential EquationsResearch Paper

Algebraic complexity theory asks how many additions and multiplications are needed to compute a polynomial. Next to exact computation it studies approximate computation: a polynomial fff is in the border of a class of circuits if circuits from the class, with constants depending on a parameter ε\varepsilonε, compute f+εgf+\varepsilon gf+εg, so that fff is their limit as …

36 thms1 active userReviewed
Functional AnalysisLinear algebraMarkov Chain·Captain: iris

Recursive Operator Localization and Spectral Gap Descent via the Geometry of Local Spectral ExpansionResearch Paper

Lower bounds on spectral gaps control the directions outside the kernel of a positive operator: the gap of a Hamiltonian above its ground-state energy, or the gap of a reversible Markov generator above its stationary subspace. For large systems such bounds are hard to obtain directly. Local-to-global methods combine tractable local estimates with control of…

34 thms1 active userReviewed
Complexity TheoryMathematical Logic·Captain: iris

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of RelationsResearch Paper

Tarski showed in the 1940s that, over binary relational signatures, three-variable first-order logic (FO3\mathrm{FO}^3FO3) and the calculus of relations (CoR), a variable-free algebra of binary relations, define the same binary queries (Tarski 1941; Tarski–Givant 1987). The two translations are lopsided: a CoR term TTT becomes an FO3\mathrm{FO}^3FO3 formula of size O(∣T∣)O(|T|)O(∣T∣)…

22 thms1 active userReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Agnostic Learning by ImitatingResearch Paper

Given a class CCC of models c:X→[−1,1]c:X\to[-1,1]c:X→[−1,1] and labeled data (x,y)∈X×{±1}(x,y)\in X\times\{\pm1\}(x,y)∈X×{±1}, two learning goals relative to CCC are standard. Agnostic learning (Haussler 1992; Kearns, Schapire and Sellie 1994) asks for a predictor whose absolute error is nearly as small as that of the best model in CCC. Multiaccuracy (Trevisan, Tulsiani and Vadhan 2009; Hébert-Johnson,…

13 thms1 active userReviewed
Control TheoryDynamical SystemsMathematical Logic+1·Captain: Shuze Chen

Global asymptotic stability of homogeneous polynomial vector fields is undecidableResearch Paper

A differential equation can have a simple finite description while its solutions have complicated long-term behavior. In control theory, one basic question is whether every state eventually approaches an equilibrium and whether starting close to it guarantees remaining close. An algorithm answering that question for every polynomial vector field would…

22 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication ComplexityResearch Paper

Communication complexity measures how many bits participants must exchange when each sees only part of an input. In the number-on-forehead model, there are kkk participants and kkk input blocks: participant iii sees every block except block iii. Their overlapping knowledge makes lower bounds difficult. A separation between randomness and nondeterminism asks whether…

13 thms1 active userReviewed
Computational GeometryDiscrete GeometryGraph Theory·Captain: iris

The Stretch Factor of Planar Delaunay Triangulations Is Nearly DeterminedResearch Paper

A Delaunay triangulation of a finite point set S⊂R2S\subset\mathbb R^2S⊂R2 is a triangulation in which the open circumdisk of every triangle contains no point of SSS. Its stretch factor is the worst ratio dD(u,v)/∥u−v∥d_D(u,v)/\|u-v\|dD​(u,v)/∥u−v∥ over pairs u≠vu\ne vu=v of SSS, where dD(u,v)d_D(u,v)dD​(u,v) is the length of a shortest path from uuu to vvv along the edges of DDD. A uniform bound ttt on this ratio makes…

32 thms1 active userReviewed
Computational ComplexityConvex OptimizationMachine Learning·Captain: iris

Universal Hardness From Masking ChannelsResearch Paper

Given a class C\mathcal CC of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling fff hard to approximate by members of C\mathcal CC? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every c∈Cc\in\mathcal Cc∈C errs on a δ\deltaδ-fraction of inputs, then there is a measure μ\muμ of…

31 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Asymptotically Optimal Weighted Edge Colorings via Local Bin PackingResearch Paper

In weighted edge coloring each edge of a graph carries a weight in (0,1](0,1](0,1], and a coloring is feasible when, at every vertex, the edges of each color have total weight at most one. The problem generalizes ordinary edge coloring (all weights one) and bin packing (a star). Its principal application is multirate routing in three-stage Clos networks, where…

20 thms1 active userReviewed
Information TheoryProbabilityStatistics·Captain: iris

Functional inequalities from the fundamental limits of Bayesian estimationResearch Paper

Functional inequalities bound how much a function can fluctuate under a probability measure by the size of its gradient. The two central examples are the Poincaré inequality, which bounds the variance, and the log-Sobolev inequality, which bounds the entropy [Gro75]. Their constants control the mixing times of Langevin diffusions and Markov chains, the…

26 thms1 active userReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

Polynomial Time Algorithms for the Kadison-Singer ProblemResearch Paper

The Kadison–Singer problem (Kadison and Singer, 1959) asks whether every pure state on the algebra of bounded diagonal operators on ℓ2\ell_2ℓ2​ extends uniquely to a pure state on all bounded operators. It has many equivalent forms; the one used here is Weaver's conjecture KS2 (Weaver, 2004): there are absolute constants α>0\alpha>0α>0 and c<1c<1c<1 such that every family …

55 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Tight Query Depth of Recursive Randomized Greedy MISResearch Paper

A maximal independent set (MIS) of a graph is an inclusion-wise maximal set of pairwise nonadjacent vertices. The randomized greedy MIS (RGMIS) algorithm draws a uniformly random permutation π\piπ of the vertices, scans them in that order, and adds a vertex whenever none of its earlier neighbours has been added. Its output V∗V^*V∗ is the lexicographically first…

45 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Search and Verification for Strategyproof Facility Location on Metric GraphsResearch Paper

In facility location without money, each of nnn agents has a private ideal location on a shared space and a planner places one facility from the agents' reports. An agent's cost is its distance to the facility, and a mechanism is strategyproof (SP) when no agent can lower its cost by misreporting. On networks such as road or communication graphs the space is…

20 thms1 active userReviewed
PreviousPage 47 of 54Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen23917600
2DBdbenbenn691113
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