<p>Let $x_1,x_2,\dots x_n$ be literals.</p>

<p>Let $P(x_1,x_2,\dots,x_n)$ be a boolean function.</p>

<p>Let $d$ be the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $f(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$).</p>

<p>Is there a candidate boolean function $P(x_1,x_2,\dots,x_n)$ such that the smallest degree of $r(x_1,x_2,\dots,x_n)\in \mathbb R(x_1,x_2,\dots,x_n)$ (sum of degrees of numerator and denominator) that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $R(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$) is $d^a$ for some $a\in(0,1)$?</p>

<p>Note that $f(x_1,x_2,\dots,x_n)$ and the numerator and denominator of $r(x_1,x_2,\dots,x_n)$ can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.</p>

CC BY-SA 3.0
2014-10-17T09:48:02.767Z
What was the answer to Emil's question given in the comments to your [previous question](http://cstheory.stackexchange.com/questions/27051/representing-boolean-function-by-a-rational-function)
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-17T16:41:24.623Z
I have made a new comment there.
Turbo
CC BY-SA 3.0
2014-10-19T05:35:19.160Z
@KristofferArnsfeltHansen Is there a positive answer for the question here?
Turbo
CC BY-SA 3.0
2014-10-19T13:37:09.587Z
I am not aware of any, but I haven't really worked with rational representation.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-19T17:50:49.703Z
@KristofferArnsfeltHansen Thank you for the answer. Atleast would you know of a paper or a reference that covers this topic?
Turbo
CC BY-SA 3.0
2014-10-19T21:16:57.820Z
I am not aware of any references that cover the question, and actually as far as I know it is still an open problem to prove a significant separation. As I recall, Lance Fortnow considered the problem once, motivated by some oracle separations.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-19T21:17:42.060Z
@KristofferArnsfeltHansen Thank you very much. Do you know which paper by Fortnow?
Turbo
CC BY-SA 3.0
2014-10-19T21:19:23.823Z
There is no paper!
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-19T21:20:03.833Z
thank you very much again but atleast do you know the separations he considered to work on? That could be a better than nothing or so lead on the topic.
Turbo
CC BY-SA 3.0
2014-10-19T21:20:43.677Z
... and I told you all I know.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-19T21:24:25.600Z
@KristofferArnsfeltHansen The paper by nisan states a structural complexity implication if we can consider rational representations. But it does not say what implications?
Turbo
<boolean-functions>
Candidate Boolean Function with efficient rational representation compared to polynomial representation
Turbo
# Candidate Boolean Function with efficient rational representation compared to polynomial representation

(Asked by: username_0 on 2014-10-17)

Let $x\_1,x\_2,\dots x\_n$ be literals.

Let $P(x\_1,x\_2,\dots,x\_n)$ be a boolean function.

Let $d$ be the smallest degree of $f(x\_1,x\_2,\dots,x\_n)\in \mathbb R[x\_1,x\_2,\dots,x\_n]$ that represents $P(x\_1,x\_2,\dots,x\_n)$ (where represents means $f(x\_1,x\_2,\dots,x\_n)$ and $P(x\_1,x\_2,\dots,x\_n)$ agree on $x\_i\in\{0,1\}$).

Is there a candidate boolean function $P(x\_1,x\_2,\dots,x\_n)$ such that the smallest degree of $r(x\_1,x\_2,\dots,x\_n)\in \mathbb R(x\_1,x\_2,\dots,x\_n)$ (sum of degrees of numerator and denominator) that represents $P(x\_1,x\_2,\dots,x\_n)$ (where represents means $R(x\_1,x\_2,\dots,x\_n)$ and $P(x\_1,x\_2,\dots,x\_n)$ agree on $x\_i\in\{0,1\}$) is $d^a$ for some $a\in(0,1)$?

Note that $f(x\_1,x\_2,\dots,x\_n)$ and the numerator and denominator of $r(x\_1,x\_2,\dots,x\_n)$ can be multilinear since $x\_i^t=x\_i$ on $\{0,1\}$.

**Tags:** boolean-functions

> **Comments:**
> **username_1**: What was the answer to Emil's question given in the comments to your [previous question](http://cstheory.stackexchange.com/questions/27051/representing-boolean-function-by-a-rational-function)  
> **username_0**: I have made a new comment there.  
> **username_0**: @KristofferArnsfeltHansen Is there a positive answer for the question here?  
> **username_1**: I am not aware of any, but I haven't really worked with rational representation.  
> **username_0**: @KristofferArnsfeltHansen Thank you for the answer. Atleast would you know of a paper or a reference that covers this topic?  
> **username_1**: I am not aware of any references that cover the question, and actually as far as I know it is still an open problem to prove a significant separation. As I recall, Lance Fortnow considered the problem once, motivated by some oracle separations.  
> **username_0**: @KristofferArnsfeltHansen Thank you very much. Do you know which paper by Fortnow?  
> **username_1**: There is no paper!  
> **username_0**: thank you very much again but atleast do you know the separations he considered to work on? That could be a better than nothing or so lead on the topic.  
> **username_1**: ... and I told you all I know.  
> **username_0**: @KristofferArnsfeltHansen The paper by nisan states a structural complexity implication if we can consider rational representations. But it does not say what implications?  

---

## 0 answers

