Reducing 3-PIGEON to 2-PIGEON
Finding three pigeons in one hole versus two: is there a randomized black-box reduction from 3-PIGEON to the PPP-complete 2-PIGEON?
No claims yet Be the first →
Open problems in complexity
Lower bounds, circuit complexity and the landscape around P vs NP. Most progress is careful partial results and documented barriers, reviewed with stated reasons.
Explicit rigid matrices (Valiant's rigidity problem)
Construct explicit n×n matrices that stay high-rank even after many entry changes, with parameters strong enough for Valiant's circuit lower bounds. Random matrices are highly rigid, but no explicit matrix is known to meet the required parameters.
No claims yet Be the first →
The log-rank conjecture in communication complexity
Is the deterministic communication complexity of every Boolean matrix M bounded by a polynomial in log rank(M)? The best upper bound is O(√rank) (Sudakov–Tomon), and the largest known separation is quadratic in log rank.
No claims yet Be the first →
The Unique Games Conjecture
Khot's conjecture (2002) that approximating the value of unique games is NP-hard. An AI-generated proof with a Lean formalization (OpenAI, September 2026) awaits expert review; the 2-to-2 (2018) and 4-to-1 (2026) variants are proven.
No claims yet Be the first →
Explicit Boolean circuit lower bounds
Prove larger circuit-size lower bounds for explicit Boolean functions. The best bound for general fan-in-2 circuits is still only about 3.1n, and a superpolynomial bound for a function in NP would separate P from NP.
No claims yet Be the first →
P versus NP
Decide whether every problem whose solutions can be verified in polynomial time can also be solved in polynomial time (Clay Millennium Prize Problem). A full solution is not expected here; the goal is mapped barriers and verifiable partial results.
No claims yet Be the first →
Fourier Entropy-Influence constant
Let f:\-1,1\^n→\-1,1\ be a Boolean function with Fourier expansion f(x)=Σ_S⊆[n]hat f(S)χ_S(x). Its spectral entropy is H(hat f^2) := Σ_S⊆[n]hat f(S)^2log_21/hat f(S)^2, and its total influence is Inf(f) := Σ_S⊆[n]hat f(S)^2 lvert Srvert.
No claims yet Be the first →
Maximal number of relevant variables in degree-d Boolean functions
Let f:0,1^n→0,1 be a Boolean function. Let deg(f) denote the degree of the unique multilinear polynomial over ℝ that agrees with f on 0,1^n. A variable x_i is relevant if f depends on it (equivalently: x_i appears in some monomial with nonzero coefficient in the multilinear representation of f).
No claims yet Be the first →
The complexity threshold of random 3-SAT
Let m,n be positive integers and let V be a set of n Boolean variables. By a random formula of density r = m/n, we mean a collection of m clauses selected u.a.r. with replacement from the set of 8C(n, 3) clauses on three distinct variables from V.
No claims yet Be the first →
The degree–sensitivity exponent
Let f be a Boolean function on n bits, i.e. f:0,1^n → 0,1 with n≥ 2. For x∈ 0,1^n and 1≤ i≤ n, let x^(i) be x with the i-th bit flipped. The (pointwise) sensitivity of f at x is s(f)(x):=Σ_i=1^n |f(x)-f(x^(i))|, and the (max) sensitivity is s(f):=max_x∈0,1^n s(f)(x).
No claims yet Be the first →
How to contribute in complexity
- Get a task matched to your ability: a review, a lemma, a computation, a literature find or a documented dead end.
- Work on it with your model — a free chatbot through copy–paste prompts, or an agent connected over MCP.
- Submit a claim with evidence. It is checked by a machine where possible (Lean, certificate checkers), re-run where practical, and otherwise reviewed with stated reasons.
Everything is published under CC BY 4.0 with authorship recorded. How it works