6

What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?

Turbo
  • 12,812
  • 1
  • 19
  • 68
  • 1
    Can you give an example of a rational function representing a Boolean function? – Yuval Filmus Oct 14 '14 at 01:48
  • @YuvalFilmus I am thinking along the same lines as representation in this question http://cstheory.stackexchange.com/questions/27042/representing-boolean-function-by-a-polynomial where $p(x)$ is replaced by $p(x)/q(x)$. – Turbo Oct 14 '14 at 04:23
  • I'm not sure there are any non-trivial examples, but before thinking about it, I was interested whether you knew about any. – Yuval Filmus Oct 14 '14 at 13:23
  • 2
    Exactly how is the representation defined? Specifically, do you demand that $q(x)\ne0$ for all $x\in{0,1}^n$, or is it sufficient if the rational function has an appropriate limit at these points? – Emil Jeřábek Oct 14 '14 at 16:09
  • 2
    (A case in point: $(x^3+y^3)/(x^2+y^2)$ uniquely extends to a total real-analytic function that defines $x\lor y$ on ${0,1}^2$, and the two polynomials have no common divisor, nevertheless they both vanish at $(0,0)$.) – Emil Jeřábek Oct 14 '14 at 18:00
  • 2
    Actually, if this is allowed, it gives a nontrivial example for the question: the function $x_1\lor\dots\lor x_n$ requires polynomials of degree $n$, but can be expressed by the degree 3 rational function $(x_1^3+\dots+x_n^3)/(x_1^2+\dots+x_n^2)$. – Emil Jeřábek Oct 14 '14 at 18:40
  • What is the polynomial for the OR function? (I guess you can recursively use the polynomial for $x_1 \vee x_2$) – Turbo Oct 15 '14 at 00:10
  • 1
    $1-(1-x_1)\cdots(1-x_n)$. – Emil Jeřábek Oct 15 '14 at 09:23
  • @EmilJeřábek missed the question. the rational function needs to have exact valuation at given points (should not be a limit). – Turbo Oct 17 '14 at 16:40

0 Answers0