Conjectured improved Junta approximation for low-influence Boolean functions
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.