Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ is the minimum degree of all polynomials over $\mathbb{R}^n$ that taking the same values of $f$ in $\{0,1\}^n$.

  • 1
    $\begingroup$ Can you share with us what progress you've made on this? What are the best lower and upper bounds you've come up with so far? As explained in help center, "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing" $\endgroup$
    – D.W.
    Jun 9 '19 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.