Suppose that you are given an algorithm A that finds the optimal solution to the shortest lattice vector problem (SVP) in time $t(n)$

I am trying to solve the Small even set problem (SES) using it: The input is a set $S$ of $m$ vectors $v_1,...,v_m$ with each $v_i$ in $\{0,1\}^d$. The goal is to find a non-empty small subset $S' \subset S$ of vectors such that $\sum_{i\in S'}v_i$ gives a vector all whose entries are even. (If addition is performed modulo 2, this corresponds to a 0-vector). Suppose S is such so that there are two small disjoint subsets $S_1, S_2$ such that $\sum_{i\in S_1}v_i= \sum_{j\in S_2}v_j$ (Observe that $S_1 \cup S_2$ is a solution to SES).

How can I use algorithm A (which does not know $S_1$ and $S_2$) in order to solve SES in size at most $|S_1| + |S_2|$, in time $t(m+d)\cdot(m+d)^{O(1)}$?



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.