Hardness of approximating the weight enumerator of a binary linear code
| dc.creator | Vyalyi, M. N. | |
| dc.date | 2003-04-30 | |
| dc.date.accessioned | 2026-07-07T03:19:38Z | |
| dc.date.available | 2026-07-07T03:19:38Z | |
| dc.description | We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is an oracle answering the solution of the evaluation problem then P^WE=P^GapP. Also we consider the approximative evaluation of the weight enumerator. In the case of approximation with additive accuracy $2^{αn}$, $α$ is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point $e^{πi/4}$ is hard for $0<\al<\al_0\approx0.88$. | |
| dc.description | 7 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0304044 | |
| dc.identifier | http://arxiv.org/abs/cs/0304044 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31541 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Hardness of approximating the weight enumerator of a binary linear code | |
| dc.type | text |