Timeline for Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2011 at 18:32 | comment | added | Peter Shor | The LLL algorithm often gives answers that are much better than the theoretical guarantee. | |
| Mar 15, 2011 at 15:52 | comment | added | David | Interesting idea, although the LLL algorithm only seems to guarantee that the basis b_1, b_2,....,b_(m-n+2) () satisfies: $|b_i| \le \exp(ci)$ ... so for large i the vectors b_i may still be very large. But maybe for the specific class of A I have in mind they turn out to be short. Maybe I'll run some simulations to find out. () Not sure if that's really the dimension of the lattice. | |
| Mar 15, 2011 at 14:51 | vote | accept | David | ||
| Mar 15, 2011 at 14:51 | |||||
| Mar 15, 2011 at 12:58 | history | answered | Roland Bacher | CC BY-SA 2.5 |