Benjamini–Kalai–Schramm noise-stability conjectures for threshold circuits

Let ff be a Boolean function, and let MM and DD 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 ff is represented by a monotone threshold circuit of size MM and depth DD, then ff is stable under (1/t)(1/t)-noise for t=(logM)100Dt=(\log M)^{100D}. (ii) If ff is monotone and represented by a threshold circuit of size MM and depth DD, then ff is stable under (1/t)(1/t)-noise for t=(logM)100Dt=(\log M)^{100D}. 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

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.