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
Operations ResearchProbabilityTheoretical Computer Science·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 LearningProbabilityTheoretical Computer Science·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
Computational ComplexityLogicTheoretical Computer Science·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
Graph TheoryProbabilityTheoretical Computer Science·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
Complexity 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
Convex OptimizationProbabilityTheoretical Computer Science·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
Graph 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
ProbabilityTheoretical 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
Quantum Information·Captain: mikedeng1

Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space StabilityResearch Paper

Locality asks how far information must travel in a network before each node can choose its part of a global solution. The basic model is the LOCAL model (Linial 1992; Peleg 2000): nodes communicate in synchronous rounds, and the round complexity of a problem is the number of rounds needed. Colouring a cycle is the standard test case. For every fixed q≥3q\ge3q≥3, qqq…

24 thms2 active usersReviewed
Mathematical PhysicsProbability·Captain: iris

Coupling Independence Implies Zero-FreenessResearch Paper

The antiferromagnetic Potts model assigns one of qqq colors to each vertex of a finite graph G=(V,E)G=(V,E)G=(V,E) and weights a coloring σ\sigmaσ by zmG(σ)z^{m_G(\sigma)}zmG​(σ), where mG(σ)m_G(\sigma)mG​(σ) is the number of monochromatic edges and the edge activity zzz lies in [0,1][0,1][0,1]. At z=0z=0z=0 its partition function counts proper qqq-colorings. Complex zeros of the partition function in the activity (Fis…

26 thms2 active usersReviewed
Information TheoryProbabilityRandom Matrix Theory+1·Captain: Shuze Chen

Product Expansion of Random Codes via Analytic TechniquesResearch Paper

Recent constructions of asymptotically good quantum LDPC codes, of classical locally testable codes with constant rate, distance and locality, and of quantum locally testable codes all follow one pattern: a high-dimensional expander lifts a small, constant-size tensor code to a large code with good parameters (Panteleev–Kalachev 2022; Dinur–Evra–Livne–Lubotz…

22 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Deterministic Fault-Tolerant Connectivity Oracles with Subqadratic SpaceResearch Paper

A fault-tolerant connectivity oracle preprocesses a graph GGG once and then answers questions about G−FG-FG−F for failure sets FFF of edges that arrive later: are two vertices still connected, or what are the connected components? Such oracles are studied as data structures, as labeling schemes, and as one-way communication protocols, and the central resource is the s…

20 thms2 active usersReviewed
AlgebracryptographyInformation Theory+1·Captain: Shuze Chen

Mutual Correlated Agreement and List-Decoding: Improvements and SeparationsResearch Paper

Interactive oracle proofs (IOPs) for proximity to Reed–Solomon and other linear codes, the engine of hash-based succinct arguments such as FRI, STIR and WHIR, repeatedly fold several words into one random linear combination and test only the combination. Soundness needs a guarantee in the other direction: if the combined word is close to the code, the input…

17 thms2 active usersReviewed
Theoretical Computer Science·Captain: Shuze Chen

Greedy BST is O(log log n)-competitiveResearch Paper

A binary search tree (BST) on the keys 1,…,n1,\dots,n1,…,n answers a sequence of searches. A balanced tree costs O(log⁡n)O(\log n)O(logn) per search, but an adaptive tree that reshapes itself can do much better on structured sequences: repeated requests, sequential scans, requests clustered in time or in key order. The dynamic optimality problem asks whether a single online BST…

15 thms2 active usersReviewed
Graph TheoryOptimal TransportTheoretical Computer Science·Captain: Shuze Chen

Graph Similarity Meets Optimal TransportResearch Paper

A common way to measure how different two graphs are is to align their vertex sets and count how much the adjacency structure disagrees under the alignment. With different matrix norms this gives graph edit distance, a standard tool in pattern recognition and graph matching (Gao et al. 2010); local edit distance, the largest number of edits needed at a…

21 thms2 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

Ranking Beats 1-1/e on General GraphsResearch Paper

A matching in a graph is a set of edges no two of which share an endpoint. Greedy matching algorithms are the default in settings where a maximum matching is too expensive to compute or where decisions must be made in a fixed order without revision: online matching, the stochastic query-commit model of kidney exchange and online dating, and streaming. The…

19 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Nearly Tight Low-Stretch Ramsey Spanning TreesResearch Paper

Embeddings of metric spaces into trees and ultrametrics are a standard tool for approximation algorithms, distance oracles and compact routing: a problem on a general metric is solved on a tree and the answer is mapped back, at the price of the distortion. The metric Ramsey theorem (Bartal, Linial, Mendel, Naor 2005; Mendel, Naor, FOCS 2006) says that every …

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

Sensitivity and Locality Lower Bounds via Low-Soundness Label CoverResearch Paper

An algorithm is sensitive when a small edit to its input can force a large change in its output. Low sensitivity matters for dynamic and streaming computation, where outputs should change little between consecutive inputs, for stability and privacy, and for distributed computing, where a sensitivity lower bound turns into a locality lower bound. Varma and…

19 thms2 active usersReviewed
Computational ComplexityLinear algebraTheoretical Computer Science·Captain: Shuze Chen

More on Correlation Bounds for PolynomialsResearch Paper

How well can low-degree polynomials over F2\mathbb F_2F2​ predict an explicit Boolean function? Small correlation with all degree-ddd polynomials is the input to the polynomial method for circuit lower bounds (Razborov, Smolensky) and a prerequisite for progress on questions in multiparty communication, matrix rigidity and pseudorandomness (see Viola's survey [5], …

24 thms2 active usersReviewed
Computational ComplexityProbabilityTheoretical Computer Science·Captain: Shuze Chen

Tight Bounds for Conservative Pointer JumpingResearch Paper

In the number-on-the-forehead (NOF) model of communication of Chandra, Furst and Lipton (CFL83), an input is split into kkk parts and each of kkk players sees every part except the one on its own forehead. Lower bounds in this model are hard to prove because the players' views overlap so much, and they would be valuable: by Yao (Yao90), Håstad and Goldmann (HG91…

19 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Recognizing Label-Connected GraphsResearch Paper

In the classical gossiping problem every participant holds one piece of information, and whenever two participants call each other they exchange everything they know. With all pairs allowed to call, 2n−42n - 42n−4 calls are necessary and sufficient for n≥4n \ge 4n≥4 participants (Baker–Shostak 1972; Hajnal–Milner–Szemerédi 1972). When the available calls are prescribed…

19 thms2 active usersReviewed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation SchemesResearch Paper

Weighted edit distance and other string alignment problems are computed by combining boundary-to-boundary distance matrices of planar alignment graphs. These matrices are Monge: Mij+Mi+1,j+1≤Mi,j+1+Mi+1,jM_{ij}+M_{i+1,j+1}\le M_{i,j+1}+M_{i+1,j}Mij​+Mi+1,j+1​≤Mi,j+1​+Mi+1,j​. For unweighted alignment, Tiskin showed that the matrices have a compact structure: O(n)O(n)O(n) space and O(nlog⁡n)O(n\log n)O(nlogn)-time min-plus products. That…

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

Constrained Directed Separation: Algorithms and ClassificationsResearch Paper

Directed Multicut asks to delete at most kkk nonterminal vertices of a digraph so that no directed path remains from the first to the second terminal of any demand. Olkowski and Ramanujan study what happens when the deleted vertices must also satisfy a structural condition: the subdigraph they induce must belong to a fixed hereditary class H\mathcal HH.…

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

Once-Paid Subsequences and the Cost of Min-Plus ApproximationResearch Paper

Many sequence problems are solved by a prefix recurrence that uses only minimum and addition, and such a recurrence, once its structure is fixed before the costs are known, is a min-plus circuit. Lower bounds on min-plus circuits therefore say which recurrences cannot exist, independently of how clever the choice of states is (Jukna–Seiwert 2020).

18 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Online Graph Exploration under T-Interval ConnectivityResearch Paper

A mobile agent that discovers a network one hop at a time cannot plan from a complete map. If links change while it moves, connectivity at each instant does not by itself let the agent reach every vertex. This matters for the mathematical foundations of exploration in changing networks: the assumption must constrain how connectivity persists, rather than…

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