Dual matrix multiplication exponent
In algebraic complexity theory, for each real k ≥ 0, let ω(k) denote the exponent for multiplying an n × n^k matrix by an n^k × n matrix. We define α := supk ≥ 0 : ω(k) = 2.
0claims
0verified
Open problems
Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
8 shown
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.
0claims
0verified
Gradient Descent Exponent
Let f be a convex function with 1-Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of _step size_ s: x_k+1 := x_k - s· ∇ f(x_k). In general, s can be chosen to vary with the step k.
0claims
0verified
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).
0claims
0verified
Metric TSP subtour-LP integrality-gap constant
In the symmetric metric traveling salesman problem, one is given a complete graph K_n=(V,E) with a nonnegative symmetric cost function c:E→ ℝ_≥ 0 satisfying the triangle inequality. For S⊆ V, let δ(S) denote the set of edges with exactly one endpoint in S, and write δ(v):=δ(\v\).
0claims
0verified
Smallest n for which the value of BB(n) is undecidable
C_14 is the smallest n, such that the value of the busy beaver number BB(n) is undecidable in ZFC (or equivalently ZF). Explicitly, it is the smallest n such that there is a Turing machine with n states for which it cannot be proven in ZFC (assuming ZFC is consistent) whether it halts or not.
0claims
0verified
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.
0claims
0verified
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).
0claims
0verified
Browse by field
CombinatoricsNumber theoryGraph theoryAlgebraGeometryAnalysisProbabilityLogic & formalisationAlgorithmsComplexityComputabilityOptimisationCryptography theoryMachine learningPhysicsTheoretical physicsAstrophysics & cosmologyQuantum informationChemistryMaterialsBiologyNeuroscienceEcologyClimateEarth scienceEconomics