| Presentation | 2010-10-15 Finding a Most-Likely Solution of the Perturbed κLIN Problem Osamu WATANABE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The kLIN problem is a problem of solving a system of linear equations over GF(2) such that each equation consists of k variables. We consider some random model for generating perturbed kLIN problem instances and discuss the average-case complexity of finding its most-likely solution. In particular, we consider the case where k=3 and give some simple algorithms that solve the problem efficiently on average. Some theoretical analysis supporting our preliminary computer experiments is also given. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | MAX-3LIN / MAX-3XORSAT / average-case analysis / message passing algorithm / local search algorithm / spectral analysis |
| Paper # | COMP2010-37 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/10/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Finding a Most-Likely Solution of the Perturbed κLIN Problem |
| Sub Title (in English) | |
| Keyword(1) | MAX-3LIN |
| Keyword(2) | MAX-3XORSAT |
| Keyword(3) | average-case analysis |
| Keyword(4) | message passing algorithm |
| Keyword(5) | local search algorithm |
| Keyword(6) | spectral analysis |
| 1st Author's Name | Osamu WATANABE |
| 1st Author's Affiliation | Department of Mathematical and Computing Sciences Tokyo Institute of Technology() |
| Date | 2010-10-15 |
| Paper # | COMP2010-37 |
| Volume (vol) | vol.110 |
| Number (no) | 232 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |