Timeline for Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1
Current License: CC BY-SA 3.0
10 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jan 5, 2014 at 20:44 | vote | accept | CommunityBot | ||
Dec 26, 2013 at 8:48 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
Sasho's comment fix
|
Dec 26, 2013 at 8:36 | comment | added | Marzio De Biasi | @SashoNikolov: yes, I mean that for every pair $(x_{2i-1},x_{2i})$ (and in the proof $(x'_{2i-1}, x'_{2i})$) exactly one is included in $X_1$; I'll edit the answer | |
Dec 26, 2013 at 7:46 | comment | added | Sasho Nikolov | also I believe you mis-state the even-odd partition problem. if no two consecutive vectors can be in the same set the problem is trivial. i believe you mean that $|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$ is required for all $i \in \{1, 2\}$ and $1 \leq j \leq m$ | |
Dec 26, 2013 at 0:41 | comment | added | Sasho Nikolov | what you call 0-1 vector partition is equivalent to the problem of determining if a set system has discrepancy 0. this is NP hard, since it captures e.g. the 2-2-set-splitting problem, see thm 9 in this paper by guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps; my paper has a bit more on the hardness of discrepancy paul.rutgers.edu/~anikolov/Files/charikarM.pdf | |
Dec 25, 2013 at 21:30 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
0-1 vector equal subset sum details
|
Dec 25, 2013 at 21:25 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
0-1 vector equal subset sum details
|
Dec 25, 2013 at 20:36 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
exponent fixed in the even odd reduction
|
Dec 25, 2013 at 19:51 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
added 118 characters in body
|
Dec 25, 2013 at 19:45 | history | answered | Marzio De Biasi | CC BY-SA 3.0 |