| Presentation | 1998/3/19 Approximating Radius and Covering Radius of Nonlinear Codes Is Hard TOSHIYA ITOH, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For a code C over GF(2), the radius and covering radius of C are useful metric properties of C and play important roles in the analysis of C.In general, the decision problem for the radius and covering radius of C is computationally hard.Indeed, the decision problem for the covering radius of linear codes over GF(2)is Il^p_<2->complete and the decision problems for the radius and covering radius of nonlinear general (not necessarily linear)codes over GF(2)is NP-complete. In this paper, we first formalize those decision problems for the radius and covering radius of codes over GF(2)as minimization problems, i.e., MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2), respectively.Then we show that MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2)are hard to approximate within any constant ratio unless P=NP. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Approximation Algorithms / Nonlinear Codes / Radius / Covering Radius |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 1998/3/19(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 | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Approximating Radius and Covering Radius of Nonlinear Codes Is Hard |
| Sub Title (in English) | |
| Keyword(1) | Approximation Algorithms |
| Keyword(2) | Nonlinear Codes |
| Keyword(3) | Radius |
| Keyword(4) | Covering Radius |
| 1st Author's Name | TOSHIYA ITOH |
| 1st Author's Affiliation | Department of Information Processing Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology() |
| Date | 1998/3/19 |
| Paper # | |
| Volume (vol) | vol.97 |
| Number (no) | 612 |
| Page | pp.pp.- |
| #Pages | 12 |
| Date of Issue | |