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 TheoryInformation TheoryTheoretical Computer Science·Captain: iris

Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy RateResearch Paper

A randomness extractor turns weakly random bits into nearly uniform ones. Cryptographic protocols, derandomization and Ramsey-graph constructions all need such objects, and in cryptographic uses the error must be negligible, not merely small. A single weak source admits no deterministic extractor, so the standard model asks for a function of two independent…

36 thms3 active usersReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: Shuze Chen

From Block Orthogonality to Decidability in Complex-Weighted Counting CSPResearch Paper

Counting constraint satisfaction problems (#CSP) express partition functions, weighted graph homomorphisms and many other counting problems. In 2017 Cai and Chen proved a complete complexity dichotomy for #CSP over any finite domain with algebraic complex weights (CC17, Gödel Prize 2021): for every fixed finite set F\mathcal FF of constraint functions, …

26 thms3 active usersReviewed
Graph TheoryTheoretical Computer ScienceTopology·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
Complexity TheoryInformation TheoryProbability+1·Captain: Shuze Chen

Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper

Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nnn nodes, or a forest, is written as a word of 2n2n2n brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…

18 thms3 active usersReviewed
Computational ComplexityGraph Theory·Captain: Shuze Chen

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable DecompositionResearch Paper

Minimum Bisection asks whether the vertex set of a graph can be split into two halves, up to one vertex, with at most kkk edges between them. It is the unweighted two-part case of the graph-partitioning problem of Kernighan and Lin (1970) and is NP-complete (Garey, Johnson and Stockmeyer, 1976). Parameterized by the cut size kkk, it became a test case for the…

29 thms3 active usersReviewed
Complexity TheoryGroup TheoryLinear algebra+1·Captain: Shuze Chen

Group Isomorphism: Depth-2122\frac{1}{2}221​ Circuits and Lower BoundsResearch Paper

Group Isomorphism (GpI) asks whether two finite groups, each given by its full multiplication table (its Cayley table), are isomorphic. With n=∣G∣n=|G|n=∣G∣, Miller's generator-enumeration algorithm decides it in time nlog⁡2n+O(1)n^{\log_2 n+O(1)}nlog2​n+O(1), because every group of order nnn is generated by at most log⁡2n\log_2 nlog2​n elements. Whether GpI is in polynomial time is open, and so is the…

17 thms3 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

3SUM Made Simpler (Without Matrix Multiplication), kkk-SUM Hypothesis Refuted for Odd kkk, and Real 3SUM/APSP DerandomizedResearch Paper

The 3SUM problem asks whether numbers from given collections satisfy an additive relation. Its running time matters in fine-grained complexity, where reductions compare the computational costs of different problems. A batch version asks which of many query numbers belong to a sumset. It retains information that a single yes-or-no decision discards, and…

12 thms3 active usersReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: iris

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold RateResearch Paper

Shamir secret sharing (Shamir 1979) encodes a secret as the values of a random polynomial at nnn points: any kkk of these shares determine the secret, and any k−1k-1k−1 of them reveal nothing. It is a basic building block of secure multiparty computation, where reconstruction thresholds near n/2n/2n/2 and n/3n/3n/3 are standard.

35 thms3 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: Shuze Chen

A Counting Lemma for Somewhat Restricted 3-APsResearch Paper

Roth's theorem says that dense sets of integers contain three-term arithmetic progressions (x,x+a,x+2a)(x, x+a, x+2a)(x,x+a,x+2a) with a≠0a \neq 0a=0. Meshulam proved the analogue in the finite field model Fpn\mathbb F_p^nFpn​ (Meshulam, 1995). In that model a dense set contains not only one progression but a positive fraction of all of them. This counting statement follows from the existence…

27 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Min-Color Path with Bounded Color-DegreeResearch Paper

A robot that must move from sss to ttt through a field of obstacles, or a signal that must cross a sensor field, wants to cross as few obstacles as possible. Discretized, this is Min-Color Path: the obstacles become colors on the vertices of an arrangement graph and one asks for an sss–ttt path touching the fewest colors. The problem appears as Minimum Constraint…

26 thms3 active usersReviewed
Discrete GeometryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

An Almost-Linear Time Algorithm for Multidimensional Subset SumResearch Paper

Subset Sum asks whether some sub-multiset of given integers sums to a target. It is one of Karp's 21 NP-complete problems, and its pseudo-polynomial complexity is a long-standing benchmark: Bellman's dynamic program runs in O(nt)O(nt)O(nt) time, Pisinger's algorithm in O(nN)O(nN)O(nN) for items bounded by NNN, and a line of work brought the bound down to O~(n+N5/3)\tilde O(n+N^{5/3})O~(n+N5/3) (Pola…

21 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized LeaderResearch Paper

A balanced vertex separator removes a small set of vertices so that no remaining connected component contains most of the original graph. Such separators allow a graph problem to be divided into smaller instances. Their usefulness depends on both the number of removed vertices and the time spent finding them: a small separator with expensive construction…

25 thms3 active usersReviewed
Complexity TheoryGraph TheoryProbability+1·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 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Counterexamples to the Strong Roberson ConjectureResearch Paper

Lovász proved in 1967 that two finite graphs are isomorphic if and only if they have the same number of homomorphisms from every finite graph. Restricting the source graphs to a class F\mathcal FF gives a coarser equivalence, homomorphism indistinguishability over F\mathcal FF, and many equivalences of theoretical computer science are of this form: Dvořák…

31 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Structural Origins of Cubic Complexity in Pebble MotionResearch Paper

In the pebble motion problem, labelled pebbles sit on distinct vertices of a graph, and a move slides one pebble along an edge onto an empty vertex. The task is to transform an initial placement into a target placement. The 15-puzzle is the best-known instance. The problem is a basic model of reconfiguration under exclusion constraints, and it underlies…

18 thms3 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: iris

Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-CompleteResearch Paper

Vector addition systems (VAS), equivalently Petri nets, are a standard model of concurrent systems with unbounded resources: processes, tokens, counters that can be incremented and decremented but never go below zero. The central algorithmic question is reachability: can a given target configuration be reached from a given source? Its decidability (Mayr…

41 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: Shuze Chen

Fatness and FlatnessResearch Paper

The theory of sparsity of Nešetřil and Ossona de Mendez describes the algorithmically useful structure of sparse graph classes. Its central notion, nowhere denseness, has many equivalent definitions. Two of them matter here. The first says that, for every radius rrr, contracting disjoint connected subgraphs of radius at most rrr cannot produce arbitrarily large…

20 thms3 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Kernelization lower bound for Permutation Pattern Matching: No polynomial kernel unless NP is contained in co-NP/polyResearch Paper

A long ordering can contain a much shorter ordering without sharing any of its numerical values. What matters is the relative order of selected entries. Researchers studying permutation patterns ask both how many permutations avoid a prescribed pattern and how efficiently an occurrence can be found. The algorithmic question has a second dimension: whether a…

15 thms3 active usersReviewed
Complexity Theory·Captain: mikedeng1

NP-Hardness of Coloring 222-Colorable 333-Uniform Hypergraphs with Ω~(log⁡log⁡n)\tilde{\Omega}(\sqrt{\log \log n})Ω~(loglogn​) ColorsResearch Paper

A hypergraph coloring assigns a color to each vertex and requires that every edge contain at least two colors. Even when a coloring with two colors exists, finding a coloring with a larger permitted palette can be computationally difficult. For ordinary graphs the two-colorability promise permits an efficient algorithm. For edges of size three, it leads to…

26 thms3 active usersReviewed
🏆Completed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Algebraic Geometry·Captain: mikedeng1

Toward Algebraic Geometry of Fixed-Parameter Tractability: Case StudiesResearch Paper

A hitting set selects vertices so that every input hyperedge contains a selected vertex. In the parameterized problem, the question is whether a hitting set of size at most a given number kkk exists. Even when a small solution exists, the collection of feasible solutions can be large. For algorithms that retain possible certificates, the relevant question is…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

The Local Query Complexity of Greedy Coloring and Other Extendable Labeling ProblemsResearch Paper

A graph may be too large for an application to construct and store a complete solution before answering its first question. A local computation algorithm instead answers questions about individual vertices through queries to the underlying graph. Its answers must remain consistent with one solution of the whole graph. The relevant resource here is the…

23 thms3 active usersReviewed
🏆Completed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov BoundResearch Paper

An insertion or deletion changes the positions of later symbols. A receiver therefore faces uncertainty about alignment as well as about the values of damaged bits. Edit-correcting codes address this problem by restricting the transmitted words so that nearby received sequences identify a unique original message. File synchronization is one concrete…

33 thms3 active usersReviewed
PreviousPage 12 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