You are given an $n$-variable multilinear polynomial (can assume of degree 2 if it helps) from an $n$-dimentional cube $p:[-1,1]^n\to\mathbb{R}$ and two vertices $v,u\in\{-1,1\}^n$. Our goal is to find a curve $\gamma: [0,1] \to [-1,1]^n$ between $u$ and $v$ which maximizes $\min_{t\in[0,1]}{p\big(\gamma(t)\big)}$.
For now, I am not even sure what fields should I consider and study before approaching this question and I would appreciate any help and directions.
Thank you all for your help in advance.
Note: After viewing that nothing helpful can be said on general polynomials, I've edited the question to be on multilinear ones.
Your hope to achieve $\min_t p(\gamma(t))\geq 0.5\min\{p(u),p(v)\}$ is unfortunately impossible: even when $n=1$ with $u=-1, v=1$, we can force $\min_t p(\gamma(t))$ to be as small as we want regardless of $p(u)$ and $p(v)$ by considering $p(x)=a(x-1)(x+1)$ for $a$ arbitrarily large (since $p(0)=-a$, but $p(u)=p(v)=0$). This example can easily be generalized to any dimension.
Furthermore, a path $\gamma$ which maximizes $\min_t p(\gamma(t))$ may not even always exist. Let $\mathcal{C}$ denote the set of curves $\gamma\colon [0,1]\to [-1,1]^n$ with $\gamma(0)=u$, $\gamma(1)=v$, and consider the function $f\colon \mathcal{C}\to\mathbb{R}$ taking $\gamma\to\min_t p(\gamma(t))$. With the metric $d(\gamma, \theta)=\sup_t|\gamma(t),\theta(t)|$, $f$ is continuous, but $C$ is not compact, so it is not guaranteed that $f$ will achieve its supremum (although there may be another way to approach this problem).
Finally, if you are simply looking to find an algorithm to approximate such a curve, I would consider taking a straight line from $u$ to $v$, and then moving each $\gamma(t)$ along the gradient at that point for each time step (in a similar fashion to what @CyclotomicField suggested). It might be worth adjusting the size of your time steps according to the degree of $p$.
Edit: As suggested in the comment, consider the case when $p(x)$ is multilinear, writing $p(x)=a_1x_1+\dots+a_nx_n+c$. We claim that, in this case, taking $\gamma$ to be the straight line between $u$ and $v$ will yield precisely $\min_tp(\gamma(t))=\min\{p(u),p(v)\}$. Indeed, let $\gamma(t)=t\cdot u+(1-t)\cdot v$. Then, $$p(\gamma(t))=c+\sum_{k=1}^na_k\left(tu_k+(1-t)v_k\right),$$ which is a linear function in $t$, and hence must reach its minimum on $[0,1]$ at one of the endpoints.