Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Combinatorics

1,238 missions · 706 completed

The mathematics of finite and discrete structures — counting the arrangements of a set, deciding when a configuration meeting prescribed constraints can exist, and characterizing the patterns such structures are forced to contain. It encompasses enumerative and extremal combinatorics, graph theory, design theory, and additive combinatorics, with deep ties to algebra, probability, and computer science.

Missions

Open532Completed706All1238
Complexity Theory·Captain: mikedeng1

Streaming Weighted Set Cover Requires (Nearly) Linear SpaceResearch Paper

In streaming set cover, mmm sets over an nnn-element universe arrive one at a time; an algorithm makes a few passes with limited memory and must approximate the minimum total weight of a cover. Storing the input costs Θ(mn)\Theta(mn)Θ(mn) bits, the incidence matrix. Running time is unrestricted, so the question is purely about information: how much memory a given number…

12 thms2 active usersReviewed
🏆Completed
Machine LearningModel Theory·Captain: mikedeng1

Encoding orders and trees in real-valued functionsResearch Paper

A bounded real-valued function can encode both branching choices and an ordered sequence of comparisons. Relating these two patterns matters in model theory, where the absence of long order patterns expresses stability, and in learning theory, where branching patterns measure sequential complexity. Conant and Terry study this relationship for functions…

16 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: iris

Subset Sum in Almost-Linear TimeResearch Paper

Subset Sum asks, for integers 1≤a1,…,an≤Δ1\le a_1,\dots,a_n\le\Delta1≤a1​,…,an​≤Δ and a target ttt, whether some sub-collection sums to ttt. It is NP-hard, but solvable in pseudopolynomial time: Bellman's dynamic program takes O(n2Δ)O(n^2\Delta)O(n2Δ) time. The fine-grained question is how fast it can be solved in terms of nnn and Δ\DeltaΔ. Under the Strong Exponential Time Hypothesis no …

31 thms2 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

An O~(n3)\widetilde{O}(n^3)O(n3)-time FPRAS for the PermanentResearch Paper

The permanent of an n×nn\times nn×n matrix A=(aij)A=(a_{ij})A=(aij​) is per(A)=∑σ∈Sn∏i=1nai,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​ai,σ(i)​. For a 0/1 matrix it counts the perfect matchings of the bipartite graph G=(V1∪V2,E)G=(V_1\cup V_2,E)G=(V1​∪V2​,E) whose adjacency matrix is AAA. Valiant showed in 1979 that computing it exactly is #P-complete even for 0/1 matrices, so the question became how fast it…

30 thms2 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: Shuze Chen

Discrete Isoperimetric Inequalities via CurvatureResearch Paper

Isoperimetric inequalities on the Boolean hypercube relate the variance of a Boolean function f:{±1}n→{±1}f:\{\pm1\}^n\to\{\pm1\}f:{±1}n→{±1} to how often flipping one coordinate changes its value. They drive sharp-threshold theorems, junta approximation, noise sensitivity, percolation, social choice and hardness of approximation (O'Donnell, Analysis of Boolean Functions, 2014).…

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

Deterministic Connectivity Sketches Under Edge DeletionsResearch Paper

A graph is to be compressed so that, after any set of its edges is deleted, one can still tell whether the remaining graph is connected. The question links one-way communication, fault-tolerant connectivity oracles, and single-pass dynamic graph streaming. With randomness it is well understood: the linear sketches of Ahn, Guha and McGregor (AGM12) use …

25 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Monotone Local Search with Sample-Dependent Running TimesResearch Paper

Many exact exponential-time algorithms solve a subset problem: the solutions of an instance are subsets of a universe of nnn elements, and the task is to decide whether a solution of a given size kkk exists. Monotone Local Search (Fomin, Gaspers, Lokshtanov, Saurabh, J. ACM 2019) turns an extension algorithm into a subset algorithm. The extension algorithm is…

11 thms2 active usersReviewed
Group TheoryProbability·Captain: Shuze Chen

Sharp Second-Order Thresholds for Random Algebraic CoverageResearch Paper

From kkk elements of an abelian group one obtains 2k2^k2k indexed subset sums; in a noncommutative group the analogous objects are products taken in the original input order. A basic all-target question is when these representations reach every element of the group. Erdős and Rényi studied this model for arbitrary finite groups, including noncommutative ones, and…

22 thms2 active usersReviewed
Computational ComplexityGraph TheoryLinear algebra+1·Captain: Shuze Chen

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper

A graph homomorphism partition function assigns to a symmetric weight matrix M∈Rn×nM\in\mathbb R^{n\times n}M∈Rn×n and a graph G=(V,E)G=(V,E)G=(V,E) the number

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

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic WeightsResearch Paper

Counting complexity asks which weighted sums over exponentially many assignments can be evaluated exactly in polynomial time. The Holant framework expresses such sums by placing a local function on every vertex of a graph and a Boolean variable on every edge. One then multiplies the local values and sums over all edge assignments (Valiant 2008; Cai–Lu–Xia…

22 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: Shuze Chen

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid ProphetResearch Paper

In the classical secretary problem (Dynkin 1963; Lindley 1961) nnn distinct values arrive in uniformly random order and the decision maker must accept or reject each one immediately and irrevocably. The aim is to select the largest. Rejecting about the first n/en/en/e values and then taking the first value larger than all earlier ones succeeds with probability…

11 thms2 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Subgaussian Vector Balancing by an Ising ModelResearch Paper

Vector balancing asks how to choose signs for short vectors so that their sum remains controlled in every direction. A distribution over signs offers a probabilistic version: every linear measurement of the resulting signed sum should have a small exponential moment. This is useful when a randomized assignment must balance several numerical covariates…

17 thms2 active usersReviewed
Computational ComplexityLinear algebra·Captain: mikedeng1

Kadison–Singer in Deterministic Polynomial TimeResearch Paper

Matrix discrepancy asks how to assign plus and minus signs to a collection of matrices so their signed sum is small. A bound independent of the matrix dimension is useful when the matrices represent many simultaneous quadratic measurements: cancellation must hold in every direction, rather than for a single scalar sum. The Kadison–Singer problem, in its…

20 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Language Generation Beyond Adversarial ExamplesResearch Paper

Researchers in learning theory study whether examples of an unknown language suffice to generate new valid strings. The task asks for a new member of the target language after each received example, with errors allowed during an initial finite period. Language generation in the limit, introduced by Kleinberg and Mullainathan, supplies a mathematical model…

28 thms2 active usersReviewed
🏆Completed
Theoretical 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…

17 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Even Coarse Matching Estimates Require Nearly Linear Streaming SpaceResearch Paper

A streaming algorithm reads graph updates in sequence while retaining a limited memory state. For matching, there is a practical distinction between storing an actual set of disjoint edges and reporting only how many edges an optimal such set contains. A large matching itself takes substantial space to write down, whereas its size is a single number. This…

17 thms2 active usersReviewed
Computational GeometryTheoretical Computer Science·Captain: Shuze Chen

Dynamic Optimality to within O(log log log n)Research Paper

A binary search tree (BST) that restructures itself while serving lookups can adapt to the access pattern: frequently or recently accessed keys can be kept near the root. The dynamic optimality conjecture of Sleator and Tarjan (1985) asks whether a single online algorithm, splay trees in their formulation, is within a constant factor of the best offline…

23 thms2 active usersReviewed
🏆Completed
Graph TheoryMathematical PhysicsProbability·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
Computational GeometryOperations ResearchOptimization·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
Complexity TheoryMachine LearningProbability·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
Graph 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
Graph 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
Number 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
Information TheoryRepresentation TheoryTheoretical Computer Science·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
Graph 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
PreviousPage 27 of 50Next

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