3
$\begingroup$

Suppose we have a function $f(x,y,z)$ where the inputs are uniform from 0 to 1. The output is either $+1$ or $-1$. And there is a partial symmetry $f(x,y,z) = f(z,y,x)$.

Tell me what the minimum of this expression is over all functions $f$: $$ E[f(a,b,c)f(b,c,d) + f(a,b,c) f(c,d,e)] $$

One way you can view this problem is finding the optimal "filling" of a cube, where the "filling" corresponds to the $+1$ region(s).

I am quite sure the optimal value is $-4/9 + 1/12 = -13/36$, with the associated function $f' = 1$ iff $2b > a+c$ and $-1$ otherwise. I think I can prove it is optimal among fillings that are half-spaces (imagine a plane cutting through the cube, and filling one side). But how can I prove this is optimal among all such functions $f$?

I've run numerics, discretizing each input to $n\le 5$ points, that suggest the optimal value is at most (but not too far from) $-0.3$.

Improve this question
$\endgroup$
1
  • $\begingroup$ Letting $g(a,b) = E_c f(a,b,c)$, then the problem is equivalent to min $E_{a,b} g(a,b)g(b,a) + E_a (E_b g(a,b))^2$ subject to $|g(a,b)| \leq 1$. This is a quadratic programming problem over an (infinite dimensional) hypercube, which is NP-hard in general, but maybe there is a simple way to show that half-spaces are optimal? $\endgroup$
    – Chris Jones
    Jan 5, 2022 at 18:30

0

Reset to default

Your Answer

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