On Restricting No-Junta Boolean Function and Degree Lower Bounds by Polynomial Method

Chia-Jung Lee, Satya V. Lokam, Shi-Chun Tsai +1

Let ${\mathcal{F}}_n^{\ast }$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $f\in {\mathcal{F}}_n^{\ast }$, $f{|}_{x_i=0}$ or $f{|}_{x_i=1}$ depends on the…