Article

Free access

Algorithmic complexity in coding theory and the minimum distance problem

Author:

Alexander VardyAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 92 - 109

https://doi.org/10.1145/258533.258559

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

M. AJTAI, Generating hard instances of lattice problems, in Proc. 28-th Annum ACM Syrup. Theory of Computing, pp. 99-108, Philadelphia, PA, May 1996.

Digital Library

Google Scholar

[2]

N. ALON, Packings with large minimum kissing numbers, preprint, 1996.

Google Scholar

[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.

Crossref

Google Scholar

[4]

S. ARORA, Probabilistic checking of proofs and hardness of approximation problems, Ph.D. thesis, University of California, Berkeley, CA., 1994.

Digital Library

Google Scholar

[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.

Google Scholar

[6]

S. ARORA and C. LUND, Hardness of approximations, in Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum (Ed.), Boston: PWS Publishing Co., pp. 399-446, 1997.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[8]

R. BALASUBRAMANIAN, M. FELLOWS, and V. RAMAN, An improved fixed-parameter algorithm for vertex cover, to appear, 1997.

Google Scholar

[9]

A. BARG, Some new NP-complete coding problems, Probl. Peredachi Informatsii, voi. 30, pp. 23-28, 1994, (in Russian).

Google Scholar

[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.

Google Scholar

[11]

E.R. BERLV. KAMP, Algebraic Coding Theory, New York: McGraw-Hill, 1968.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Digital Library

Google Scholar

[16]

J. BRUCK and M. NAOR, The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, vol. 36, pp. 381-385, 1990.

Digital Library

Google Scholar

[17]

G.C. CLARK and J.B. CAIN, Error-Correction Coding for Digital Communications, New York: Plenum Press, 1981.

Digital Library

Google Scholar

[18]

R.G. DOWNS7 and M.R. FELLOWS, Fixed parameter tractability and completeness I: basic theory, SIAM J. Comput., vol. 24, pp. 873-921, 1995.

Digital Library

Google Scholar

[19]

R.G. DowNEY and M.R. FELLOWS, Fixed parameter tractability and completeness II: completeness for WIll, Theoret. Computer Sci. A vol. 141 pp. 109-131, 1995.

Digital Library

Google Scholar

[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.

Google Scholar

[21]

P. DIACONIS and R.L. GRAHAM, The Radon transform on Z~, Pacific J. Math., vol. 118, pp. 176-185, 1985.

Crossref

Google Scholar

[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).

Google Scholar

[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.

Google Scholar

[24]

S. EVEN and Y. YACOBI, Cryptography and NP-completeness, Lect. Notes Comp. Science, vol. 85, pp. 195- 207, Springer-Verlag, 1982.

Digital Library

Google Scholar

[25]

J. FANG, G.D. COHEN, PH. GODLEWSKI, and G.BAT- TAIL, On the inherent intractability of soft decision decoding of linear codes, Lect. Notes Comp. Science, vol. 311, pp. 141-149, Springer-Verlag, 1988.

Digital Library

Google Scholar

[26]

R.M. FANO, A heuristic discussion of probabilistic decoding, IEEE Trans. Inform. Theory, vol. 9, pp. 64-73, 1963.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[29]

M.R. FELLOWS and A. VARDY, The hardness of theta series in lattices, preprint in preparation, 1997.

Google Scholar

[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.

Digital Library

Google Scholar

[31]

G.D. FORNEY, JR., Concatenated Codes, Cambridge, MA: M.I.T. Press, 1966.

Google Scholar

[32]

G.D. FORNEV, JR., The Viterbi algorithm, Proc. IEEE, vol. 61, pp. 268-278, 1973.

Crossref

Google Scholar

[33]

G.D. FORNEY, JR., Convolutional codes III: sequential decoding, Inform. Control, vol. 25, pp. 267-297, 1974.

Crossref

Google Scholar

[34]

G.D. FORN~.Y, JR., Coset codes II: Binary lattices and related codes, IEEE Trans. Inform. Theory, vol. 34, pp. 1152-1187, 1988.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[38]

R.G. GALLAGER, Low Density Parity-Check Codes, Cambridge: M.I.T. Press, 1962.

Google Scholar

[39]

M.R. GARSY and D.S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco: Freeman, 1979.

Digital Library

Google Scholar

[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.

Google Scholar

[41]

D.S.HOCHBAUM, (Editor), Approximation Algorithms for NP-Hard Problems, Boston: PWS Publishing Co., 1997.

Digital Library

Google Scholar

[42]

T. HOHOLDT and R. PELLIKAAN, On the decoding of algebraic-geometric codes, IEEE Trans. Inform. Theory, vol. 41, pp. 1589-1614, 1995.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[44]

D.S. JOHNSON, The NP-completeness column: An ongoing guide, J. Algorithms, vol. 3, pp. 182-195, 1982.

Crossref

Google Scholar

[45]

D.S. JOHNSON, The NP-completeness column: An ongoing guide, J. Algorithms, vol. 7, pp. 584-601, 1986.

Digital Library

Google Scholar

[46]

J. JUSTESEN, A class of constructive asymptotically good algebraic codes, IEEE Trans. Inform. Theory, vol. 18, pp. 652-656, 1972.

Crossref

Google Scholar

[47]

R. KARP and R. LIPTON, Some connections between nonuniform and uniform complexity classes, in Proc. 12-th Annual Syrup. Theory of Computing, pp. 302- 309, 1980.

Digital Library

Google Scholar

[48]

L. KHACHtYAN, On the complexity of approximating extremal determinants in matrices, J. Complexity, vol. 11, pp. 138-153, 1995.

Digital Library

Google Scholar

[49]

F.R. KSCHmCHANG and V. SOROKINE, Oll the trellis structure of block codes, IEEE Trans. Inform. Theory, vol. 41, pp. 1924-1937, 1995.

Crossref

Google Scholar

[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).

Google Scholar

[51]

A. LAFOURCADF. and A. VARDY, Asymptotically good codes have infinite trellis complexity, IEEE Transl Inform. Theory, vol. 41, pp. 555-559, 1995.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[53]

L.A. LE:WN, Average case completeness, SIAM J. Cornput., vol. 15, pp. 285-286, 1986.

Digital Library

Google Scholar

[54]

S. LIN and E.J. WELDON, Long BCH codes are bad, Inform. and Control, vol. 11, pp. 445-451, 1967.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[56]

B. LdPr. Z JIM~.NrZ, Plane models of Drinfeld modulax curves, Ph.D. thesis, University of Complutense, Madrid, March 1996.

Google Scholar

[57]

D.J.C. MACKAY and R.M. NEAL, Near Shannon limit performance of low-density parity-check codes, Elect. Lett., to appear, 1997.

Google Scholar

[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.

Digital Library

Google Scholar

[59]

F.J. MACWmLIAMS and N.J.A. SLOANS, The Theory of Error Correcting Codes, Amsterdam: North-Holland, 1977.

Google Scholar

[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).

Crossref

Google Scholar

[61]

J.L. MASSrY, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, vol. 15, pp. 122-127, 1969.

Crossref

Google Scholar

[62]

J.L. MASSE:Y, Foundation and methods of channel encoding, Proc. Int. Cone Information Theory and Systems, NTG-Fachberichte, Berlin, 1978.

Google Scholar

[63]

R.J. M cELmcP, On the BCJR trellis for linear block codes, IEEE Trans. Inform. Theory, vol. 42, pp. 1072- 1092, 1996.

Digital Library

Google Scholar

[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.

Google Scholar

[65]

D.J. MUDER, Minimal trellises for block codes, IEEE Trans. Inform. Theory, vol. 34, pp. 1049-1053, 1988.

Crossref

Google Scholar

[66]

T. MUIR, Treatise on the Theory of Determinants, New York: Dover, 1960.

Google Scholar

[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.

Digital Library

Google Scholar

[68]

J.K. OMURA, On the Viterbi decoding algorithm, IEEE Trans. Inform. Theory, vol. 15, pp. 177-179, 1969.

Crossref

Google Scholar

[69]

J. PEARL, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, San Mateo, CA: Kaufmann, 1988.

Digital Library

Google Scholar

[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.

Google Scholar

[71]

I.S. REED and G. SOLOMON, Polynomial codes over certain finite fields, SIAM J. Appl. Math., vol. 8, pp. 300- 304, 1960.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[73]

C.E. SHANNON, A mathematical theory of communication, Bell Syst. Tech. J., voi. 27, pp. 379-423 and pp. 623-656, 1948.

Google Scholar

[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.

Crossref

Google Scholar

[75]

V. SHOUP, New algorithms for finding irreducible polynomials over finite fields, Math. Computation, vol. 54, pp. 435-447, 1990.

Crossref

Google Scholar

[76]

M. SIPSER and D.A. SPIELMAN, Expander codes, IEEE Trans. Inform. Theory, vol. 42, pp. 1710-1722, 1996.

Crossref

Google Scholar

[77]

D.A. SPmLMAN, Linear-time encodable and decodable codes, IEBE Trans. Inform. Theory, vol. 42, pp. 1723- 1731, 1996.

Crossref

Google Scholar

[78]

J. STERN, Approximating the number of error locations within a constant ratio is NP-complete, Lect. Notes Comp. Science, vol. 673, pp. 325-331, Springer, 1993.

Digital Library

Google Scholar

[79]

M. SUDAN, Efficient checking of polynomials and proofs and the hardness of approximation problems, Ph.D. thesis, University of California, Berkeley, CA., 1992.

Digital Library

Google Scholar

[80]

M. SUDAN, Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, vol. 1, 1997, to appear.

Digital Library

Google Scholar

[81]

R.M. TANNER, A recursive approach to low-complexity codes, IEEE Trans. Inform. Theory, vol. 27, pp. 533- 547, 1981.

Digital Library

Google Scholar

[82]

A. TRACHTENBERG and A. VARDY, Which codes have cycle-free Tanner graphs?, preprint, 1997.

Google Scholar

[83]

M.A. TSrASMAN and S.G. VL~DUTS, Algebraic Geometry Codes, Dodrecht: Kluwer Academic, 1991.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[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).

Google Scholar

[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.

Google Scholar

[91]

N. WIBERG, Codes and decoding on general graphs, Ph.D. thesis, University of LinkSping, Sweden, 1996.

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[94]

V.V. ZYABLOV, An estimate of the complexity of constructing binary linear concatenated codes, Problemy Peredachi Informatsii, vol. 7, pp. 5-13, 1971.

Google Scholar

Cited By

View all

Ilievska N(2024)Theoretical proof for the number of errors that one linear code detects/corrects when linear quasigroups of order 4 are used for codingAsian-European Journal of Mathematics10.1142/S1793557124500529Online publication date: 12-Jul-2024
https://doi.org/10.1142/S1793557124500529
Boche HGrigorescu ASchaefer RPoor H(2024)Characterization of the Complexity of Computing the Capacity of Colored Gaussian Noise ChannelsIEEE Transactions on Communications10.1109/TCOMM.2024.338170572:8(4844-4856)Online publication date: Aug-2024
https://doi.org/10.1109/TCOMM.2024.3381705
Boche HGrigorescu ASchaefer RPoor H(2024)Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian ChannelsICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10622861(4114-4119)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10622861
Show More Cited By

Index Terms

Algorithmic complexity in coding theory and the minimum distance problem

Recommendations

The minimum Manhattan network problem: Approximations and exact solutions

Given a set of points in the plane and a constant t>=1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in ...
Minimum backward fréchet distance
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

We propose a new measure to capture similarity between polygonal curves, called the minimum backward Fréchet distance. It is a natural optimization on the weak Fréchet distance, a variant of the well-known Fréchet distance. More specifically, for a ...
On algorithmic complexity of imprecise spanners
Abstract
Let t > 1 be a real number. A geometric t-spanner is a geometric graph for a point set in R d with straight line segments between vertices such that the ratio of the shortest-path distance between every pair of vertices in the graph (with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
2,338
Total Downloads

Downloads (Last 12 months)237
Downloads (Last 6 weeks)26

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ilievska N(2024)Theoretical proof for the number of errors that one linear code detects/corrects when linear quasigroups of order 4 are used for codingAsian-European Journal of Mathematics10.1142/S1793557124500529Online publication date: 12-Jul-2024
https://doi.org/10.1142/S1793557124500529
Boche HGrigorescu ASchaefer RPoor H(2024)Characterization of the Complexity of Computing the Capacity of Colored Gaussian Noise ChannelsIEEE Transactions on Communications10.1109/TCOMM.2024.338170572:8(4844-4856)Online publication date: Aug-2024
https://doi.org/10.1109/TCOMM.2024.3381705
Boche HGrigorescu ASchaefer RPoor H(2024)Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian ChannelsICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10622861(4114-4119)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10622861
Chrisnata JKiah HVardy AYaakobi E(2023)Bee Identification Problem for DNA StrandsIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2023.32944234(190-204)Online publication date: 2023
https://doi.org/10.1109/JSAIT.2023.3294423
Chara MKottler SMalmskog BThompson BWest M(2023)Minimum distance and parameter ranges of locally recoverable codes with availability from fiber products of curvesDesigns, Codes and Cryptography10.1007/s10623-023-01189-691:5(2077-2105)Online publication date: 4-Mar-2023
https://doi.org/10.1007/s10623-023-01189-6
Prabowo TTan C(2023)Attack on a Code-Based Signature Scheme from QC-LDPC CodesCodes, Cryptology and Information Security10.1007/978-3-031-33017-9_9(136-149)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33017-9_9
Sekiguchi TTanaka H(2023)Security Enhancement Method Using Shortened Error Correcting CodesCodes, Cryptology and Information Security10.1007/978-3-031-33017-9_23(379-394)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33017-9_23
Yin HNg KMa SWong HMak H(2022)Two-State Alien Tiles: A Coding-Theoretical PerspectiveMathematics10.3390/math1016299410:16(2994)Online publication date: 19-Aug-2022
https://doi.org/10.3390/math10162994
Chrisnata JKiah HVardy AYaakobi E(2022)Bee Identification Problem for DNA Strands2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834414(969-974)Online publication date: 26-Jun-2022
https://doi.org/10.1109/ISIT50566.2022.9834414
Bhattacharyya ABonnet ÉEgri LGhoshal SS. KLin BManurangsi PMarx D(2021)Parameterized Intractability of Even Set and Shortest Vector ProblemJournal of the ACM10.1145/344494268:3(1-40)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3444942
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The minimum Manhattan network problem: Approximations and exact solutions

Minimum backward fréchet distance

On algorithmic complexity of imprecise spanners