Chen's few-subpowers expressive-rate conjecture

From papers

Let Γ\Gamma be a constraint language, and let r(n)r(n) be the logarithm of the number of distinct nn-variable relations definable by primitive positive formulas over Γ\Gamma. Chen's expressive-rate conjecture. The function r(n)r(n) always either grows as a polynomial or as an exponential function. In the polynomial-growth case, the class of definable relations is efficiently learnable and the associated CSP can be solved in polynomial time. The surrounding text says that this conjecture was resolved through the theory of algebras with few subpowers.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Zarathustra Brady, “Notes on CSPs and Polymorphisms”, arXiv:2210.07383 (2025).

Solutions 0

No solutions have been posted yet.