Low-influence approximation conjecture for Boolean functions
Low-influence approximation conjecture for Boolean functions
For a Boolean function , define its total influence by
A Boolean function -approximates when . Low-influence approximation conjecture. For some absolute constant , every Boolean function can be -approximated by a circuit of depth and size satisfying
This is proposed as a reverse-Håstad-type statement and remains open in the supplied text.
Sources & referencesView supporting material
Primary source
Gil Kalai, “Three Puzzles on Mathematics, Computation, and Games”, arXiv:1801.02602 (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
Sign in to submit a solution.
No solutions have been posted yet.