Anthony–Brightwell–Shawe-Taylor characterization conjecture for the minimum specification number

Let f535nf535^n denote the Boolean cube, let f539nf539_n be the class of threshold Boolean functions on nn variables, and let f539f539n(f)f539_{f539_n}(f) denote the specification number of ff within this class. A linear read-once function is a Boolean function computed by a linear read-once formula. Anthony–Brightwell–Shawe-Taylor's conjecture. If f\throughinf539nf\throughin f539_n has specification number n+1n+1, then ff is linear read-once. The conjecture asserts that the linear read-once functions are exactly the threshold functions attaining the lower bound n+1n+1; the supplied text does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Vadim Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva and Nikolai Yu. Zolotykh, “Linear read-once and related Boolean functions”, arXiv:1805.10159 (2018).

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.