Vladimir Levenshtein

Vladimir Iosifovich Levenshtein (Russian: Влади́мир Ио́сифович Левенште́йн, IPA: [vlɐˈdʲimʲɪr ɪˈosʲɪfəvʲɪtɕ lʲɪvʲɪnˈʂtʲejn] (listen); March 20, 1935 – September 6, 2017) was a Russian scientist who did research in information theory, error-correcting codes, and combinatorial design.[1] Among other contributions, he is known for the Levenshtein distance and a Levenshtein algorithm, which he developed in 1965.

Vladimir Levenshtein
Born
Vladimir Iosifovich Levenshtein

(1935-05-20)20 May 1935
Moscow, USSR
Died6 September 2017(2017-09-06) (aged 82)
NationalityRussian
CitizenshipRussia
Alma materMoscow State University
Known forLevenshtein distance
Levenshtein automaton
Levenshtein coding
AwardsIEEE Richard W. Hamming Medal (2006)
Scientific career
FieldsMathematics

He graduated from the Department of Mathematics and Mechanics of Moscow State University in 1958 and worked at the Keldysh Institute of Applied Mathematics in Moscow ever since. He was a fellow of the IEEE Information Theory Society.

He received the IEEE Richard W. Hamming Medal in 2006, for "contributions to the theory of error-correcting codes and information theory, including the Levenshtein distance".[2]


Life

Levenshtein graduated from Moscow State University in 1958, where he studied in the faculty of Mechanics and Mathematics. After graduation he worked at the M.V Keldysh Institute of Applied Mathematics.

Publications
  • Levenshtein, V. I. (1965), "Binary codes capable of correcting deletions, insertions, and reversals.", Doklady Akademii Nauk SSSR, 163 (4): 845–848
  • Delsarte, P.; Levenshtein, V. I. (1998), "Association schemes and coding theory", IEEE Transactions on Information Theory, 44 (6): 2477–2504, doi:10.1109/18.720545
  • V.I. Levenshtein, On a class of systematic codes, Dokl. USSR Academy of Sciences, 131, 5, 1960, 1011-1014.
  • V.I. Levenshtein, Application of Hadamard matrices to a problem in coding theory, Problems of Cybernetics, vol. 5, GIFML, Moscow, 1961, 125-136.
  • V.I. Levenshtein, On some properties of code systems, Dokl. USSR Academy of Sciences, 140, 6, 1961, 1274-1277.
  • V.I. Levenshtein, Self-tuning machines for decoding messages, Dokl. USSR Academy of Sciences, 141, 6, 1961, 1320-1323.
  • V.I. Levenshtein, On the inversion of finite automata, Dokl. USSR Academy of Sciences, 147, 6, 1962, 1300-1303.
  • V.I. Levenshtein, On the stable extension of finite automata, Problems of Cybernetics, vol. 10, GIFML, Moscow, 1963, 281-286.
  • V.I. Levenshtein, On some coding systems and self-tuning machines for decoding messages, Problems of Cybernetics, vol. 11, GIFML, Moscow, 1964, 63-121.
  • V.I. Levenshtein, Decoding automata invariant with respect to the initial state, Problems of Cybernetics, vol. 12, GIFML, Moscow, 1964, 125-136.
  • V.I. Levenshtein, Binary codes with correction of occurrences, inserts and symbol substitutions, Dokl. USSR Academy of Sciences, 163, 4, 1965, 845-848.
  • V.I. Levenshtein, Binary Codes with Correction of Drops and Inserts of Symbol 1, Probl. before. inform., 1, 1, 1965, 12-25.
  • V.I. Levenshtein, On a Method for Solving the Problem of Synchronizing a Circuit of Automata in Minimum Time, Probl. before. inform., 1, 4, 1965, 20-32.
  • V.I. Levenshtein, Binary codes providing synchronization and correction of errors, Abstracts of short scientific reports of the International Congress of Mathematicians, Section 13, Moscow, 1966, 24.
  • V.I. Levenshtein, Asymptotically optimal binary code with correction of occurrences of one or two adjacent characters, Problems of Cybernetics, vol. 19, Science, Moscow, 1967, 293-298.
  • V.I. Levenshtein, On the redundancy and deceleration of separable coding of natural numbers, Problems of Cybernetics, vol. 20, Nauka, Moscow, 1968, 173-179.
  • V.I. Levenshtein, On Synchronization of Bilateral Automata Networks, Probl. before. Inform., 4, 4, 1968, 49-62.
  • V.I. Levenshtein, Estimates for Codes Providing Error Correction and Synchronization, Probl. before. inform., 5, 2, 1969, 3-13.
  • V.I. Levenshtein, On the Maximum Number of Words in Codes without Overlapping, Probl. before. inform., 6, 4, 1970, 88-90.
  • V.I. Levenshtein, On One Method for Building Quasilinear Codes Providing Synchronization and Error Correction, Probl. before. inform., 7, 3, 1971, 30-40.
  • V.I. Levenshtein, Upper Bounds for Codes with Fixed Weight of Vectors, Probl. before. Inform., 7, 4, 1971, 3-12.
  • V.I. Levenshtein, On Minimum Redundancy of Binary Error Correcting Codes, Probl. before. inform., 10, 2, 1974, 26-42.
  • V.I. Levenshtein, Elements of coding theory, In the book. Discrete mathematics and mathematical questions of cybernetics, Nauka, Moscow, 1974, 207-305.
  • V.I. Levenshtein, On the maximum filling density of an n-dimensional Euclidean space with equal balls, Matematicheskie Zametki, 18, 2, 1974, 301-311.
  • VI Levenshtein, Methods for obtaining bounds in metric problems of coding theory, Proc. of the 1975 IEEE-USSR Joint Workshop on Information Theory, New York, 1976, 126-143.
  • V.I. Levenshtein, On Bounds for the Probability of Undetected Error, Probl. before. inform., 13, 1, 1977, 3-18.
  • G.A. Kabatiansky, V.I. Levenshtein, On Boundaries for Packages on the Sphere and in Space, Probl. before. inform., 14, 1, 1978, 3-25.
  • V.I. Levenshtein, On the choice of polynomials for obtaining boundaries in packaging problems, VII All-Union Conference on the Theory of Coding and Information Transfer, Part II, Moscow - Vilnius, 1978, 103-108.
  • V.I. Levenshtein, On boundaries for packings in n-dimensional Euclidean space, Dokl. USSR Academy of Sciences, 245, 6, 1979, 1299-1303.
  • V.I. Levenshtein, Bounds for the maximum power of a code with a bounded modulus of the scalar product, Dokl. USSR Academy of Sciences, 263, 6, 1982, 1303-1308.
  • V.I. Levenshtein, Borders for packaging of metric spaces and some of their applications, Problems of cybernetics, vol. 40, Science, Moscow, 1983, 43-110.
  • VI Levenshtein, Packing of polynomial metric spaces, Third International Workshop on Information Theory, Convolutional codes; multi-user communication, Sochi, 1987, 271-274.
  • V.I. Levenshtein, A Straight Linear Bound for the Exponent of the Probability of an Undetected Error, Probl. before. inform., 25, 1, 1989, 33-37.
  • VI Levenshtein, Perfect deletion-correcting codes as combinatorial designs, Proc. of the Second International Workshop: Algebraic and Combinatorial Coding Theory, Leningrad, USSR, 1990, 137-140.
  • V.I. Levenshtein, On Perfect Codes in the Metric of Insertions and Dropouts, Discrete Mathematics, 3, 1, 1991, 3-20.
  • VI Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Applicandae Mathematicae, vol. 29 (1992), 1-82.
  • VI Levenshtein, Bounds for self-complementary codes and their applications, in Eurocode-92. CISM Courses and Lectures, vol. 339. Springer-Verlag, Wien-New-York, 1993, 159-171.
  • VI Levenshtein, Bounds for codes as solutions of extremum problems for systems of orthogonal polynomials, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lectures Notes in Computer Science, vol. 673, Springer-Verlag, 1993, 25-42.
  • VI Levenshtein and AJH Vinck, Perfect (d, k) -codes capable of correcting single peak-shifts, IEEE Trans. Inform. Theory, vol. 39, no. 2 (1993), 656-662.
  • VI Levenshtein, Packing and decomposition problems for polynomial association schemes, Europ. J. Combinatorics, vol. 14 (1993), 461-477.
  • T. Ericson and VI Levenshtein, Superimposed codes in the Hamming space, IEEE Trans. Inform. Theory, vol. 40, no. 6 (1994), 1882-1893.
  • G. Fasekas and VI Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces, J. Combin. Th. Ser. A, vol. 70, no. 2 (1995), 267-288.
  • T. Helleseth, T. Klove, VI Levenshtein, and O. Ytrehus, Bounds on the minimum support weights, IEEE Trans. Inform. Theory, vol. 41, no. 2 (1995), 432-440.
  • VI Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory, vol. 41, no. 5 (1995), 1303-1321.
  • V.I. Levenshtein, A Simple Proof of the Basic Inequalities for the Fundamental Parameters of Codes in Polynomial Relationship Schemes, Probl. before. inform., 31, 4, 1995, 37-50.
  • VI Levenshtein, Reconstructing binary sequences by the minimum number of their subsequences or supersequences of a given length. Proceedings of Fifth Intern. Workshop on Algebr. and Combin. Coding Theory, Sozopol, Bulgaria, June 1-7, 1996, 176-183.
  • VI Levenshtein, Lower bounds on crosscorrelation of codes. Proceedings of IEEE Fourth Intern. Symp on Spread Spectrum Techniques and Appl., Mainz, Germany, September 22-25, 1996, 657-661.
  • VI Levenshtein, Split orthogonal arrays and maximum independent resilient systems of functions, Designs, Codes and Cryptography, vol. 12, no. 2 (1997), 131-160.
  • T. Helleseth, T. Klove, and VI Levenshtein, On the information function of an error-correcting code, IEEE Trans. Inform. Theory, vol. 43, no. 2 (1997), pp. 549-557.
  • V.I. Levenshtein, Restoration of objects from the minimum number of distorted samples, Doklady of the Russian Academy of Sciences, 354, 5, 1997, 593-596.
  • P. Delsarte and VI Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory, vol. 44, no. 6 (1998), 2477-2504.
  • VI Levenshtein, Universal bounds for codes and designs, in Handbook of Coding Theory, VS Pless and WC Huffman, Eds., Amsterdam: Elsevier, vol. 1, 499-648, 1998.
  • VI Levenshtein, On designs in compact metric spaces and a universal bound on their size, Discrete Mathematics, vol. 192 (1998), 251-271.
  • VI Levenshtein, On the maximum T-wise independent systems of Boolean functions, Workshop on Coding and Cryptography, Paris, France, 1999, 367-370.
  • VI Levenshtein, Equivalence of Delsarte's bounds for codes and designs in symmetric association schemes and some applications, Discrete Mathematics, vol. 197/198 (1999), 515-536.
  • VI Levenshtein, New lower bounds on aperiodic crosscorrelation of binary codes, IEEE Trans. Inform. Theory, vol. 45, no. 1 (1999), 284-288.
  • IN AND. Levenshtein, On designs in continuous unit cubes, Proceedings of the IV International Conference: Discrete models in the theory of control systems, Moscow State University, MAKS Press, 2000, 62-64.
  • VI Levenshtein, Efficient reconstruction of sequences, IEEE Trans. Inform. Theory, vol. 47, no. 1 (2001), 2-22.
  • VI Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, Journal of Combin. Theory, Ser. A, vol. 93, no. 2 (2001), 310-332.
  • T. Berger and VI Levenshtein, Asymptotical efficiency of two-stage testing, IEEE Trans. Inform. Theory, vol. 48, no. 7 (2002), 1741-1749.
  • T. Berger and VI Levenshtein, Application of cover-free codes and combinatorial designs to two-stage testing, Discrete Applied Mathematics.
  • T. Helleseth, T. Klove and VI Levenshtein, Hypercubic 4 and 5-designs from double-error-correcting BCH codes, Designs, Codes and Cryptography.
  • VI Levenshtein, A universal bound for a covering in regular posets and its application to pool testing, Discrete Mathematics.
  • T. Helleseth, T. Klove and VI Levenshtein, Error-correction capability of binary linear codes and the discrete simplex problem, IEEE Trans. Inform. Theory.
  • VI Levenshtein, Combinatorial problems motivated by comma-free codes, Discrete Mathematics.
gollark: Nim is an interesting possibility which I may investigate, yes.
gollark: I feel like that would just be OCaml but the ecosystem is even more nonexistent.
gollark: It has nice features but also horrible things.
gollark: I tried using it for stuff and I disliked it.
gollark: Haskell is obviously no, Python is quite slow and has different ecosystem problems as well as a remarkable amount of weird inconsistency, JS dependencies break after about 5 months and it's an awful language, Rust is somewhat nice but annoying compared to higher level languages, Clojure is maybe good however Lisp and also Java (well, JVM), and... that's about it?

See also

References
  1. "Код без ошибок". nplus1.ru (in Russian). Retrieved 2017-10-21.
  2. "IEEE Richard W. Hamming Medal Recipients" (PDF). IEEE. Retrieved May 29, 2011.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.