Algorithmic complexity in coding theory and the minimum distance problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithmic complexity in coding theory and the minimum distance problem

Full text

Pdf (2.46 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 92 - 109

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Alexander Vardy

Coordinated Science Laboratory, University of Illinois, 1308 W. Main Street, Urbana, IL

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 174, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258559 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
	2	N. ALON, Packings with large minimum kissing numbers, preprint, 1996.
	3	N. ALON, J. BRUCK, J. NAOR, M. NAOR, and R. ROTH, Construction of asymptotically good low-rate errorcorrecting codes through pseudo-random graphs, IEEE Trans. Inform. Theory, vol. 38, pp. 509-516, 1992.
	4	Sanjeev Arora, Probabilistic checking of proofs and hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1995
	5	S. ARORA, L. BABAI, J. STERN, and Z. SWEEDYK, The hardness of approximate optima in lattices, codes, and systems of linear equations, in Proc. 34-th Annum Syrup. Found. Computer Science, pp. 724-733, Palo Alto, CA, 1993.
	6	Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	7	L.R. BAHL, J. COCKE, F. JELINEK, and J. R. AVIV, Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inform. Theory, vol. 20, pp. 284- 287, 1974.
	8	R. BALASUBRAMANIAN, M. FELLOWS, and V. RAMAN, An improved fixed-parameter algorithm for vertex cover, to appear, 1997.
	9	A. BARG, Some new NP-complete coding problems, Probl. Peredachi Informatsii, voi. 30, pp. 23-28, 1994, (in Russian).
	10	A. BARG, Complexity issues in coding, survey chapter to appear in Handbook of Coding Theory, R.A. Brualdi, C. Huffman, and V. Pless (Ed.), Amsterdam: Elsevier.
	11	E.R. BERLV. KAMP, Algebraic Coding Theory, New York: McGraw-Hill, 1968.
	12	E.R. BP. RLEKAMP, R.J. McELIECF., and H.C.A.vAN TILBORG, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, vol. 24, pp. 384-386, 1978.
	13	C. BERROU, A. GLAVlEUX, and P. THITIMAJSHIMA, Near Shannon limit error-correcting coding and decoding: turbo codes, in Proc. IEEE Int. Conf. on Communications, pp. 1064-1070, Geneva, Switzerland, 1993.
	14	M. BLAUM, J. BRUCE, and A. VARDY, On MDS codes and alternants over certain rings, in Proc. 900-th Meeting, American Math. Soc., Chicago, IL., March 1995.
	15	M. BLAUM, J. BRUCK, and A. VARDY, MDS array codes with independent parity symbols, IEEE Trans. Inform. Theory, vol. 42, pp. 529-542, 1996.
	16	J. BRUCK and M. NAOR, The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, vol. 36, pp. 381-385, 1990.
	17	George C. Clark , J. Bibb Cain, Error-Correction Coding for Digital Communications, Perseus Publishing, 1981
	18	Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
	19	Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3 ]
	20	R.G.DOWNEY, M.R. FELLOWS, A.VARDY, and G.WHI- TTLE, On the parametrized complexity of certain fundamental problems in coding theory, preprint in preparation, 1997.
	21	P. DIACONIS and R.L. GRAHAM, The Radon transform on Z~, Pacific J. Math., vol. 118, pp. 176-185, 1985.
	22	I.I. DUMER, On complexity of maximum-likelihood decoding of the best concatenated codes, in Proc. 8-th All- Union Conf. on Coding Theory and Information Theory, Moscow-Kuibishev, pp. 66-69, 1981, (in Russian).
	23	I.I. DuMER, Concatenated codes and their generalizations, to appear in Handbook of Coding Theory, R.A. Brualdi, W.C. Huffman, V. Pless (Ed.), Amsterdam: Elsevier.
	24	Shimon Even , Yacov Yacobi, Cryptocomplexity and NP-Completeness, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.195-207, July 14-18, 1980
	25	J. Fang , G. Cohen , P. Godlewski , G. Battail, On the inherent intractability of soft decision decoding of linear codes, on Coding theory and applications, p.141-149, June 1988, Cachan-Paris, France
	26	R.M. FANO, A heuristic discussion of probabilistic decoding, IEEE Trans. Inform. Theory, vol. 9, pp. 64-73, 1963.
	27	J. FEIGENBAUM, The use of coding theory in computational complexity, in Proc. Syrup. Appl. Math, A.R. Calderbank (Ed.), Providence, RI: AMS Press, pp. 203-229, 1995.
	28	J. FEIGENBAUM, G.D. FORNEY, B. MARCUS, R.J. Mc ELIECE, and A. VARDY, Special issue on "Codes and Complexity," IEEE Trans. Inform. Theory, vol. 42, November 1996.
	29	M.R. FELLOWS and A. VARDY, The hardness of theta series in lattices, preprint in preparation, 1997.
	30	G.-L. FENG and K.K. TZENG, A new procedure for decoding cyclic and BCH codes up to actual minimum distance, IEEE Trans. Inform. Theory, vol. 40, pp. 1364- 1374, 1994.
	31	G.D. FORNEY, JR., Concatenated Codes, Cambridge, MA: M.I.T. Press, 1966.
	32	G.D. FORNEV, JR., The Viterbi algorithm, Proc. IEEE, vol. 61, pp. 268-278, 1973.
	33	G.D. FORNEY, JR., Convolutional codes III: sequential decoding, Inform. Control, vol. 25, pp. 267-297, 1974.
	34	G.D. FORN~.Y, JR., Coset codes II: Binary lattices and related codes, IEEE Trans. Inform. Theory, vol. 34, pp. 1152-1187, 1988.
	35	G.D. FOaNEY, Ja., The forward-backward algorithm, in Proc. 34-th Allerton Conference on Comm., Control, and Computing, Monticello, IL., pp. 432-446, October 1996.
	36	G.D. FORNF. Y, JR. and A. VARD~, Generalized minimum distance decoding of Euclidean-space codes and lattices, IEEE Trans. Inform. Theory, vol. 42, pp. 1992- 2026, 1996.
	37	B.J. FREY and F.R. KSCHmCHANG, Probability propagation and iterative decoding, in Proc. 34-th Allerton Conference on Comm., Control, and Computing, Monticello, IL., pp. 482-493, October 1996.
	38	R.G. GALLAGER, Low Density Parity-Check Codes, Cambridge: M.I.T. Press, 1962.
	39	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	40	C.R.P. HARTMAN and K.K. TZP. N6, Decoding beyond the BCH bound using multiple sets of syndrome sequences, IEEE Trans. inform. Theory, vol. 20, pp. 292- 295, 1974.
	41	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	42	T. HOHOLDT and R. PELLIKAAN, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, vol. 41, pp. 1589-1614, 1995.
	43	G.B. HOaN and F.R. KSCHmCHANG, On the intractability of permuting a block code to minimize trellis complexity, IEEE Trans. Inform. Theory, vol. 42, pp. 2042- 2048, 1996.
	44	D.S. JOHNSON, The NP-completeness column: An ongoing guide, J. Algorithms, vol. 3, pp. 182-195, 1982.
	45	David S Johnson, The NP-completeness column: An ongoing guide, Journal of Algorithms, v.7 n.4, p.584-601, Dec. 1986 [doi>10.1016/0196-6774(86)90020-9]
	46	J. JUSTESEN, A class of constructive asymptotically good algebraic codes, IEEE Trans. Inform. Theory, vol. 18, pp. 652-656, 1972.
	47	Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
	48	Leonid Khachiyan, On the complexity of approximating extremal determinants in matrices, Journal of Complexity, v.11 n.1, p.138-153, March 1995 [doi>10.1006/jcom.1995.1005 ]
	49	F.R. KSCHmCHANG and V. SOROKINE, Oll the trellis structure of block codes, IEEE Trans. Inform. Theory, vol. 41, pp. 1924-1937, 1995.
	50	B.D. KUDRYASHOV and T.G. ZAKHAaOVA, Block codes from convolutional codes, Problemy Peredachi Informats/i, vol. 25, pp. 98-102, 1989, (in Russian).
	51	A. LAFOURCADF. and A. VARDY, Asymptotically good codes have infinite trellis complexity, IEEE Transl Inform. Theory, vol. 41, pp. 555-559, 1995.
	52	A. LAFOURCADE and A. V^RDY, Lower bounds on trellis complexity of block codes, IEEE Trans. Inform. Theory, vol. 41, pp. 1938-1954, 1995.
	53	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	54	S. LIN and E.J. WELDON, Long BCH codes are bad, Inform. and Control, vol. 11, pp. 445-451, 1967.
	55	A. LOBSTEiN and G.D. COHrN, Sur la complexit~ d'un probl~me de codage, Theoretical Informatics Appl., vol. 21, pp. 25-32, 1987.
	56	B. LdPr. Z JIM~.NrZ, Plane models of Drinfeld modulax curves, Ph.D. thesis, University of Complutense, Madrid, March 1996.
	57	D.J.C. MACKAY and R.M. NEAL, Near Shannon limit performance of low-density parity-check codes, Elect. Lett., to appear, 1997.
	58	D.J.C. MACKAY and R.M. NS:AL, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, submitted for publication, 1996.
	59	F.J. MACWmLIAMS and N.J.A. SLOANS, The Theory of Error Correcting Codes, Amsterdam: North-Holland, 1977.
	60	YU.I. MANm and S.C. VL/~DUTS, Linear codes and modular curves, J. Soviet Math., vol. 30, pp. 2611-2643, 1985, (in Russian).
	61	J.L. MASSrY, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, vol. 15, pp. 122-127, 1969.
	62	J.L. MASSE:Y, Foundation and methods of channel encoding, Proc. Int. Cone Information Theory and Systems, NTG-Fachberichte, Berlin, 1978.
	63	R.J. M cELmcP,, On the BCJR trellis for linear block codes, IEEE Trans. Inform. Theory, vol. 42, pp. 1072- 1092, 1996.
	64	R.J. MCELIECE, E.R. RODEMICH, and J.-F. CHENG, The turbo decision algorithm, in Proc. 33-rd Allerton Conference on Comm., Control, and Computing, Monticello, IL., pp. 366-379, October 1995.
	65	D.J. MUDER, Minimal trellises for block codes, IEEE Trans. Inform. Theory, vol. 34, pp. 1049-1053, 1988.
	66	T. MUIR, Treatise on the Theory of Determinants, New York: Dover, 1960.
	67	S.C. NTAFOS and S.L. HAKIMI, On the complexity of some coding problems, IEEE Trans. Inform. Theory, vol. 27, pp. 794-796, 1981.
	68	J.K. OMURA, On the Viterbi decoding algorithm, IEEE Trans. Inform. Theory, vol. 15, pp. 177-179, 1969.
	69	Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	70	R. PELLIKAAN, Asymptotically good sequences of curves and codes, in Proc. 34-th A11erton Conference on Comm., Control, and Computing, Monticello, IL., pp. 276-285, October 1996.
	71	I.S. REED and G. SOLOMON, Polynomial codes over certain finite fields, SIAM J. Appl. Math., vol. 8, pp. 300- 304, 1960.
	72	R.M. RoTH and A. LEMPV~L, A construction of non- Reed-Solomon type MDS codes, IEEE 7kans. Inform. Theory, vol. 35, pp. 655-657, 1989.
	73	C.E. SHANNON, A mathematical theory of communication, Bell Syst. Tech. J., voi. 27, pp. 379-423 and pp. 623-656, 1948.
	74	B.-Z. SHEN, A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate, IEEE Trans. Inform. Theory, vol. 39, pp. 239-242, 1993.
	75	V. SHOUP, New algorithms for finding irreducible polynomials over finite fields, Math. Computation, vol. 54, pp. 435-447, 1990.
	76	M. SIPSER and D.A. SPIELMAN, Expander codes, IEEE Trans. Inform. Theory, vol. 42, pp. 1710-1722, 1996.
	77	D.A. SPmLMAN, Linear-time encodable and decodable codes, IEBE Trans. Inform. Theory, vol. 42, pp. 1723- 1731, 1996.
	78	Jacques Stern, Approximating the Number of Error Locations within a Constant Ratio is NP-complete, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.325-331, May 10-14, 1993
	79	Madhu Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1992
	80	Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439 ]
	81	R.M. TANNER, A recursive approach to low-complexity codes, IEEE Trans. Inform. Theory, vol. 27, pp. 533- 547, 1981.
	82	A. TRACHTENBERG and A. VARDY, Which codes have cycle-free Tanner graphs?, preprint, 1997.
	83	M.A. A. Tsfasman , S.G. Vladut, Algebraic-Geometric Codes, Kluwer Academic Publishers, Norwell, MA, 1991
	84	M.A. TSFASMAN, S.G. VLXDUTS, and T. ZINK, Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound, Math. Nachrichten, vol. 104, pp. 13-28, 1982.
	85	P. VAN EMDE BOAS, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Tech. Report 81-04, Dept. of Mathematics, Univ. of Amsterdam, 1980.
	86	A. VARDY, Trellis structure of block codes, to appear in Handbook of Coding Theory, R. Brualdi, W.C. Huffman, and V. Pless (Ed.), Amsterdam: Elsevier.
	87	A. VARDY and F.R. KSCHmCHANG, Proof of a conjecture of McEliece regarding the expansion index of the minimal trellis, IEEB Trans. Inform. Theory, vol. 42, pp. 2027-2033, 1996.
	88	A. VARDY, J. SNYDERS, and Y. BE'ERY, Bounds on the dimension of codes and subcodes with prescribed contraction index, Linear Algebra Appl., vol. 142, pp. 237- 261, 1990.
	89	S.G. VL/kDUTS, G.L. KATSMAN, and M.A. TSFASMAN, Modular curves and codes with polynomial complexity of construction, Problemy Peredachi Int'ormatsii, vol. 20, pp. 47-55, 1984, (in Russian).
	90	D.J.A. WELSH, Combinatorial problems in matroid theory, pp. 291-307 in Combinatorial Mathematics and its Applications, D.J.A. Welsh (Ed.), London: Academic Press, 1971.
	91	N. WIBERG, Codes and decoding on general graphs, Ph.D. thesis, University of LinkSping, Sweden, 1996.
	92	N. WmERG, H.-A. LOELIGER, and R. KOTTER, Codes and iterative decoding on general graphs, Euro. Trans. Telecommun., vol. 6, pp. 513-526, 1995.
	93	J.K. WOLF, Efficient maximum-likelihood decoding of linear block codes using a trellis, IEEE Trans. Inform. Theory, vol. 24, pp. 76-80, 1978.
	94	V.V. ZYABLOV, An estimate of the complexity of constructing binary linear concatenated codes, Problemy Peredachi Informatsii, vol. 7, pp. 5-13, 1971.

CITED BY 5

	Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.10-19, May 24-26, 1998, Dallas, Texas, United States
	M. Amin Shokrollahi , Hal Wasserman, Decoding algebraic-geometric codes beyond the error-correction bound, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.241-248, May 24-26, 1998, Dallas, Texas, United States
	Venkatesan Guruswami , Alexander Vardy, Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Bodo Manthey , Rüdiger Reischuk, The intractability of computing the Hamming distance, Theoretical Computer Science, v.337 n.1-3, p.331-346, 9 June 2005
	Oded Goldreich , Dana Ron , Madhu Sudan, Chinese remaindering with errors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.225-234, May 01-04, 1999, Atlanta, Georgia, United States