Conjectured improved Junta approximation for low-influence Boolean functions
Let be a Boolean function, write , and let denote its total influence. A function is a Junta if it depends on only a bounded number of coordinates. Improved Junta approximation conjecture. For any , any function satisfying
can be -approximated by a function that depends on at most coordinates. The paper presents this as a reasonable conjecture in its open-problems section; it would strengthen the paper's Junta approximation result for functions whose influence is close to the minimum.
References
Primary source
Nathan Keller and Noam Lifshitz, “Approximation of biased Boolean functions of small total influence by DNF's”, arXiv:1703.10116 (2017).
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
No solutions have been posted yet.