Benjamini–Kalai–Schramm noise-stability conjectures for threshold circuits
Benjamini–Kalai–Schramm noise-stability conjectures for threshold circuits
Let be a Boolean function, and let and denote the size and depth of a threshold circuit representing it. A circuit is monotone threshold when its threshold gates have nonnegative weights. Benjamini–Kalai–Schramm threshold-circuit conjectures. (i) If is represented by a monotone threshold circuit of size and depth , then is stable under -noise for . (ii) If is monotone and represented by a threshold circuit of size and depth , then is stable under -noise for . The source presents both assertions as conjectures motivated by known results and open questions about bounded-depth threshold circuits.
Sources & referencesView supporting material
Primary source
Gil Kalai, “Three Puzzles on Mathematics, Computation, and Games”, arXiv:1801.02602 (2018).
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.