<p>Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions.
Clearly we can only get the values 0 and 1 by evaluating these expressions (with an assignment to the variables).
We wish to add a quantitative element to these expressions, by means of a weighted average. We consider the following operators:
$\oplus_\lambda$, which is defined by $s\oplus_\lambda t=\lambda s+ (1-\lambda)t$, for any $\lambda\in [0,1]$.
$\otimes_\lambda$, which is defined by $s\otimes_\lambda t=\lambda \max\{s,t\}+(1-\lambda)\min\{s,t\}$.</p>

<p>Intuitively, the difference is whether we attempt to interpolate between $\min$ and $\max$, or to add an addition element.</p>

<p>The question is: is the arithmetic with $\oplus$ strictly more expressive than $\otimes$?</p>

<p>Obviously, $\otimes$ can be captured by $\oplus$, since:
$$s\otimes_\lambda t=\max\{s,t\}\oplus_\lambda \min\{s,t\}$$
For the other direction, we have a partial result:
$$(s\otimes_\lambda 0)\otimes_\frac12 (t\otimes_{1-\lambda}0)=\frac12(s\oplus_\lambda t)$$
But I can't seem to be able to get rid of that $\frac12$ (recall that $\lambda\in [0,1]$), or to prove that there is an expressiveness difference.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2012-03-02T13:04:01.270Z
$\min$, $\max$, and $\otimes_\gamma$ are all commutative.  $\oplus_\gamma$ is not (except when $\gamma = 1/2$).
Jeffε
CC BY-SA 3.0
2012-03-02T14:25:33.933Z
$\oplus_\lambda$ is not symmetric unless $\lambda=\frac{1}{2}$.
Kaveh
CC BY-SA 3.0
2012-03-02T15:40:14.087Z
As you can see, we can break the symmetry "manually", by selecting $\lambda$ according to the order of the parameters. That's how we obtain $\frac12(s\oplus_\lambda t)$ using the symmetric $\otimes$. So this doesn't prove that $\oplus$ is more expressive.
Shaull
<lo.logic><arithmetic-circuits>
Expressive power of (versions of) weighted average
Shaull
# Expressive power of (versions of) weighted average

(Asked by: username_0 on 2012-03-02)

Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions.
Clearly we can only get the values 0 and 1 by evaluating these expressions (with an assignment to the variables).
We wish to add a quantitative element to these expressions, by means of a weighted average. We consider the following operators:
$\oplus\_\lambda$, which is defined by $s\oplus\_\lambda t=\lambda s+ (1-\lambda)t$, for any $\lambda\in [0,1]$.
$\otimes\_\lambda$, which is defined by $s\otimes\_\lambda t=\lambda \max\{s,t\}+(1-\lambda)\min\{s,t\}$.

Intuitively, the difference is whether we attempt to interpolate between $\min$ and $\max$, or to add an addition element.

The question is: is the arithmetic with $\oplus$ strictly more expressive than $\otimes$?

Obviously, $\otimes$ can be captured by $\oplus$, since:
$$s\otimes\_\lambda t=\max\{s,t\}\oplus\_\lambda \min\{s,t\}$$
For the other direction, we have a partial result:
$$(s\otimes\_\lambda 0)\otimes\_\frac12 (t\otimes\_{1-\lambda}0)=\frac12(s\oplus\_\lambda t)$$
But I can't seem to be able to get rid of that $\frac12$ (recall that $\lambda\in [0,1]$), or to prove that there is an expressiveness difference.

Thanks!

**Tags:** lo.logic, arithmetic-circuits

> **Comments:**
> **username_1**: $\min$, $\max$, and $\otimes_\gamma$ are all commutative.  $\oplus_\gamma$ is not (except when $\gamma = 1/2$).  
> **username_2**: $\oplus_\lambda$ is not symmetric unless $\lambda=\frac{1}{2}$.  
> **username_0**: As you can see, we can break the symmetry "manually", by selecting $\lambda$ according to the order of the parameters. That's how we obtain $\frac12(s\oplus_\lambda t)$ using the symmetric $\otimes$. So this doesn't prove that $\oplus$ is more expressive.  

---

## 0 answers

