Constant-depth decision-tree conjecture for Boolean functions on Grassmann graphs

Let Jq(n,k)J_q(n,k) be the Grassmann graph on the kk-dimensional subspaces of an nn-dimensional vector space over the finite field of order qq. A Boolean degree dd function is a Boolean function of degree dd in the Grassmann association scheme. Constant-depth decision-tree conjecture. For every given qq and dd, there exists a k0k_0 such that if k,nkk0k,n-k\geq k_0, then every Boolean degree dd function on Jq(n,k)J_q(n,k) is a constant-depth decision tree, with queries asking whether a point is contained in a subspace or whether a subspace is contained in a hyperplane. The paper presents this as a conjecture motivated by examples; no resolution is supplied.

Sources & referencesView supporting material

Primary source

Jan De Beule, Jozefien D'haeseleer, Ferdinand Ihringer and Jonathan Mannaert, “Degree 2 Boolean Functions on Grassmann Graphs”, arXiv:2202.03940 (2022).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.