4
$\begingroup$

The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$?

The problem of max product: likewise two sets each $n$ vectors (I forgot to mention in both cases values are binary). We want to find maximal inner product (one vector from set $A$ and one from $B$).

I want to find a reduction between OV to max. Inner product.

My idea: Use negative values, claim its equivalent with negative value and possitive values.

What I mean, OV reduced to max. Inner prod with negative values by multiplying all by $-1$.

Then if maximum is zero... Orthogonality. Else, no orthogonality.

But i need to argue negative max inner product equivalent to max. Inner product.

Maybe there is another way?

If it does not work, also interested in reduction from sat.

Improve this question
$\endgroup$
2
  • $\begingroup$ What kind of reduction are you looking for? Many to one reductions? Turing reductions? $\endgroup$
    – nir shahar
    Jan 9, 2022 at 23:54
  • $\begingroup$ Turing reduction will be good, and if possible, many to one. But even turing will assiste me. $\endgroup$
    – V. Prasad
    Jan 9, 2022 at 23:56

1 Answer 1

Reset to default
5
$\begingroup$

One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$. We have $$ \langle \hat{x}, \hat{y} \rangle = \sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2. $$ Therefore if you know the minimum inner product, you can solve OV. It remains to negate all vectors in one of the sets.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is interesting. But for minimum inner product, there is no need for that simply leave the vectors as they are and then if minimal ip is 0 they are orthogonal and else they are not. My problem begins when i try reducing to maximum inner product i thought they are equivalent easily, but it required more than just multiplying by $-1$ (if simply multiply by $-1$, we get also positive values when multiplied, also to note). $\endgroup$
    – V. Prasad
    Jan 10, 2022 at 7:12
  • $\begingroup$ Use $\langle \hat x, - \hat y \rangle = -\langle x,y \rangle^2$. $\endgroup$
    – Yuval Filmus
    Jan 10, 2022 at 7:18
  • $\begingroup$ Simple and brilliant. $\endgroup$
    – John L.
    Jan 10, 2022 at 7:35
  • 1
    $\begingroup$ I gave you a start. You take it from here. $\endgroup$
    – Yuval Filmus
    Jan 10, 2022 at 11:44
  • 2
    $\begingroup$ hm but still for this i would not need to increase the dimension. leaving the data as is already is reduction from orthogonal to minimal value. increasing the dimension has didnt change $\endgroup$
    – V. Prasad
    Jan 12, 2022 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.