Constant-depth decision-tree conjecture for Boolean functions on Grassmann graphs
Constant-depth decision-tree conjecture for Boolean functions on Grassmann graphs
Let be the Grassmann graph on the -dimensional subspaces of an -dimensional vector space over the finite field of order . A Boolean degree function is a Boolean function of degree in the Grassmann association scheme. Constant-depth decision-tree conjecture. For every given and , there exists a such that if , then every Boolean degree function on 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.