sIs there any (efficient) algorithm for the following problem:

Let $n = 128$ and $m = 64$ (in the end only $n > m$ matters) and $p_1, \ldots, p_t \in \{ -1,1 \} ^{128}$ be given ($t << 2^{128}$) . Find a matrix $A \in M(n \times m, \frac{1}{2^{64}}\mathbb{Z})$ and vectors $q_1, \ldots, q_t \in \{ -1, 1 \}^{64}$, such that if $b_i = A q_i \in \mathbb{R}^{128}$ then $$p_{ij} = sgn (b_{ij})$$ for most $1 \leq i \leq t$ and $1 \leq j \leq n$, i.e., the number of tuples $(i,j)$ violating the equation is neglible compared to $tn$.

  • 2
    $\begingroup$ Please fix your typos (click the edit button). For example $b_i$ is only mentioned once. $\endgroup$ – Brendan McKay May 24 '12 at 2:10
  • $\begingroup$ So, $p_{ij}$ is your notation for the $j$th component of $p_i$, similarly, $b_{ij}$? $\endgroup$ – Gerry Myerson Jul 11 '12 at 1:27
  • $\begingroup$ Yes, that is precisely what I meant. So in essence practically everything of the vectors $p_i$ can be obtained from $A$ and the smaller vectors $q_i$. $\endgroup$ – tobias Jul 16 '12 at 14:01

Your Answer

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

Browse other questions tagged or ask your own question.