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

826–850 of 1496
Open1374Completed122All1496
CombinatoricsComplexity TheoryGraph Theory+2·Captain: Shuze Chen

Near-Linear Lower Bounds for Testing Directed AcyclicityResearch Paper

Property testing asks for algorithms that inspect a tiny part of a large object and distinguish objects with a property from objects that are far from it (Goldreich, Goldwasser, Ron 1998). For sparse directed graphs, the natural access model is the bounded-degree incidence-lists model of Bender and Ron (2002): the algorithm may ask for the outgoing edges of…

20 thms2 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Pandora's Knapsack via Simple PoliciesResearch Paper

In stochastic knapsack, items with random sizes are inserted one at a time into a knapsack of fixed capacity; an item's size is revealed only once it is inserted, and the process stops at the first overflow. Dean, Goemans and Vondrák (DGV08) showed that simple non-adaptive orderings lose only a constant factor against the best adaptive policy. Many…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryMathematical Physics+1·Captain: Shuze Chen

A Complete Hierarchy of Local LemmasResearch Paper

Suppose each vertex vvv of a graph GGG carries a bad event AvA_vAv​ with Pr⁡(Av)≤pv\Pr(A_v)\le p_vPr(Av​)≤pv​, and GGG is a dependency graph: each AvA_vAv​ is independent of the collection of events at its non-neighbors. The Lovász Local Lemma gives a local sufficient condition under which, with positive probability, no bad event occurs. Shearer (Shearer 1985) found the exact condition: writing

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

A Good Way to Find Good HypothesesResearch Paper

Hypothesis selection is the basic learning problem behind the cover method of density estimation: given nnn known distributions h1,…,hnh_1,\dots,h_nh1​,…,hn​ and samples from an unknown distribution ppp, output a distribution almost as close to ppp in total variation as the best hih_ihi​. A proper algorithm must output one of the hih_ihi​. Scheffé-type tournaments and the minimum distance…

18 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Inevitable Knowledge in Communication Complexity and the LOCAL ModelResearch Paper

A protocol that decides a property of two parties' inputs often learns more than the one bit it outputs. Grossman, Grossman, Naor and Shulman ask when this extra knowledge is inevitable: when every protocol for a decision or computation problem, whatever its design, leaves behind a transcript from which a related search problem can be solved with little…

11 thms2 active usersReviewed
Graph Theory·Captain: Shuze Chen

Maximal Isolating Vertex Cuts and Shredders: Structure and ApplicationsResearch Paper

A graph can remain connected after several vertices fail and then break into several pieces when one small set fails. The size of a smallest disconnecting vertex set measures resilience, but that number alone does not describe the failures that fragment the graph most severely. Listing the smallest cuts that produce three or more components exposes this…

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

Stacking Stars: Minimum-Area Packing with and without RotationResearch Paper

Packing irregular shapes without overlap so as to use little material is a core problem of the cutting and nesting industries (sheet metal, textiles, wood). It has a large experimental and operations-research literature and several commercial and open-source systems. The CG:SHOP 2024 challenge (Fekete et al.) was a packing problem with nonconvex objects.…

25 thms2 active usersReviewed
CombinatoricsComplexity TheoryMachine Learning+1·Captain: Shuze Chen

Learning DNF from Satisfying Assignments with Membership QueriesResearch Paper

Learning from satisfying assignments was introduced by De, Diakonikolas and Servedio (DDS15, SODA 2015). An unknown Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} from a known class is given only through independent uniform samples from its satisfying set F=f−1(1)F = f^{-1}(1)F=f−1(1), and the learner must output a sampler whose output law is close to the uniform law UFU_FUF​ in total…

24 thms2 active usersReviewed
Complexity TheoryNumerical AnalysisTheoretical Computer Science·Captain: Shuze Chen

High Precision Multiplicative-Error Approximation of #SAC¹ Functions in Logspace Uniform AC¹Research Paper

Counting computations can produce integers whose binary expansions are much longer than their inputs. A short arithmetic circuit may repeatedly multiply values, making exact output expensive even when the circuit itself has a compact description. An approximation can have a short floating-point representation, but a small absolute error does not by itself…

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

Distribution-Robust Halfspace TestingResearch Paper

A halfspace (linear classifier) x↦sign⁡(⟨w,x⟩−t)x\mapsto\operatorname{sign}(\langle w,x\rangle-t)x↦sign(⟨w,x⟩−t) is the simplest model for labelled data in Rn\mathbb R^nRn. Before training one, it is useful to know whether the labels are close to linearly separable. A property tester decides this from far less data than a learner needs, the "model selection" motivation of Goldreich,…

20 thms2 active usersReviewed
Control TheoryProbabilityStochastic Systems+1·Captain: iris

Exact Universality of Online DiscrepancyResearch Paper

In online vector balancing, vectors ξ1,…,ξN∈RM\xi_1,\dots,\xi_N\in\mathbb R^Mξ1​,…,ξN​∈RM arrive one at a time and an algorithm must fix a sign εk∈{−1,+1}\varepsilon_k\in\{-1,+1\}εk​∈{−1,+1} for each vector before the next one is revealed, so as to keep the signed sum small in every coordinate. The problem is a basic model of irrevocable decisions under uncertainty, and the same quantity governs the …

33 thms2 active usersReviewed
Computational ComplexitycryptographyQuantum Information+1·Captain: iris

Quantum Multi-Collision Lower Bounds for Arbitrary Bounded TypesResearch Paper

Collision finding is a basic benchmark of quantum query complexity and of post-quantum security: the cost of finding inputs with equal outputs bounds the security of hash functions and of protocols built from them against quantum attackers. Two refinements matter in practice. One asks for many collisions at once (security reductions for multi-instance…

31 thms2 active usersReviewed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: iris

When quantum thermal states look classicalResearch Paper

A quantum many-body system in thermal equilibrium at inverse temperature β\betaβ is described by its Gibbs state ρβ(H)=e−βH/Tr e−βH\rho_\beta(H)=e^{-\beta H}/\mathrm{Tr}\,e^{-\beta H}ρβ​(H)=e−βH/Tre−βH. At β=0\beta=0β=0 this state is maximally mixed and carries no entanglement; at low temperature it can be highly entangled. The death of entanglement is the temperature above which every Gibbs state of…

39 thms2 active usersReviewed
cryptographyDiscrete GeometryProbability·Captain: iris

Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense SublatticesResearch Paper

Lattice enumeration is the exact method for the shortest vector problem (SVP) used inside BKZ-style reduction, and BKZ is how the concrete security of lattice-based cryptography is estimated. Its cost on a basis BBB is the number of nodes T(B)T(B)T(B) of the full enumeration tree. For random lattices the tree size behaves like T(B)=ncn+o(n)T(B)=n^{cn+o(n)}T(B)=ncn+o(n), and the constant ccc deci…

44 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: iris

Universality in random graphs via optimal linking systems: trees and beyondResearch Paper

A graph GGG is universal for a family F\mathcal FF if it contains a copy of every member of F\mathcal FF as a subgraph. Sparse universal graphs for bounded-degree trees were first studied for circuit design (Friedman–Pippenger 1987; Bhatt, Chung, Leighton and Rosenberg 1989). The probabilistic question is how large ppp must be for the binomial random graph G(n,p)G(n,p)G(n,p) to…

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

Faster Isomorphism for Groups of Class 2Research Paper

The group isomorphism problem asks whether two finite groups, given by their Cayley tables (multiplication tables), are isomorphic. It lies in NP, is not known to be in P or NP-complete, and is a recognised bottleneck for graph isomorphism: Babai's quasipolynomial-time algorithm for graphs does not carry over, and the classical bound for groups of order NNN is…

24 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Sharp Spectral Bounds for Kikuchi Matrices: The Hypergraph Moore Bound and Optimal Trade-offs for kkkXORResearch Paper

A collection of parity constraints can contain a small dependency: a nonempty collection of constraints in which every variable appears an even number of times. Such dependencies are combinatorial certificates, and their size measures how far a hypergraph resembles an acyclic object. For ordinary graphs, the smallest such collection is a shortest cycle. The…

23 thms2 active usersReviewed
Convex OptimizationProbabilityRandom Matrix Theory+1·Captain: Shuze Chen

Recovering Planted Subgraphs in Smoothed ModelsResearch Paper

A graph can contain a large structured region even when the rest of the graph is unreliable. Recovering that region asks for more than detecting that it exists: an algorithm must identify most of its vertices without selecting too many unrelated ones. Random models can make this task tractable, but fully random assumptions also remove the adversarial…

26 thms2 active usersReviewed
CombinatoricsNumber TheoryTheoretical Computer Science·Captain: iris

A Complete Characterization of Eventually Evasive Binary PatternsResearch Paper

Deciding whether a fixed word occurs in a text is the most basic string-matching task. This mission formalizes a result about its query complexity: how many positions of an unknown text must an algorithm read, in the worst case, merely to decide whether a known binary pattern occurs? Computation is free and only reads are counted, so the question isolates…

29 thms2 active usersReviewed
CombinatoricsInformation TheoryRepresentation Theory+1·Captain: iris

The Honeycomb Framework for Code BoundsResearch Paper

A binary code of length nnn is a set C⊆{±1}nC\subseteq\{\pm1\}^nC⊆{±1}n; it has minimum distance at least ddd if any two distinct codewords differ in at least ddd coordinates. The rate–distance tradeoff asks for the largest size A2(n,d)A_2(n,d)A2​(n,d) of such a code, and asymptotically for

45 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Set-defined graph classes: χ\chiχ-boundedness meets tropical algebraResearch Paper

A hereditary class of graphs is χ-bounded if the chromatic number of its members is bounded by a function of their clique number, and polynomially χ-bounded if that function can be a polynomial. Deciding which natural classes are χ-bounded, and whether χ-boundedness forces polynomial χ-boundedness, is a central theme of structural graph theory…

31 thms2 active usersReviewed
🏆Completed
cryptographyProbabilityTheoretical Computer Science·Captain: iris

Correlated Group Actions: Founding Cryptography on S4 and SnResearch Paper

Oblivious transfer (OT) is a two-party primitive in which a sender holds two bits m0,m1m_0, m_1m0​,m1​, a receiver holds a selection bit sss, and the receiver learns msm_sms​ while the sender learns nothing about sss and the receiver learns nothing about the other bit m1−sm_{1-s}m1−s​. Kilian showed in 1988 that OT is complete for secure two-party computation: any function can be…

15 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

Beyond Width-3: Better Hitting Set Generators for Width-4 Read-Once Branching ProgramsResearch Paper

A computation with little working memory can still use many random bits. A read-once branching program records how its memory state changes as these bits arrive. Its width measures the number of possible states at each step, and its length counts the bits read. Finding short deterministic descriptions of useful input strings is one way to understand how…

27 thms2 active usersReviewed
Machine LearningProbability·Captain: Shuze Chen

Sample Complexity of Multiclass OmnipredictionResearch Paper

Omniprediction, introduced by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389), asks for one predictor that serves every downstream decision maker at once. Each decision maker has their own loss, best-responds to the predicted label distribution, and should do as well as the best benchmark in a fixed class FFF. For binary labels, randomized…

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

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update TimeResearch Paper

Correlation clustering asks for a partition of the vertices of a complete graph whose edges are labelled (+)(+)(+) (similar) or (−)(-)(−) (dissimilar), minimizing the number of disagreements: (+)(+)(+) edges between clusters plus (−)(-)(−) edges inside clusters. Introduced by Bansal, Blum and Chawla (DOI 10.1023/B:MACH.0000033116.57574.95), it is a standard model for…

22 thms2 active usersReviewed
PreviousPage 34 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