Necrology: C.-P. Schnorr

 
Necrology:

Claus-Peter Schnorr

(* 4 Aug. 1943 [Völkingen, Saarbrücken, Saarland, Germany] - † 8 Jun. 2025)

Professor of Mathematics and Computation {Mathematik und Informatik}, Johann Wolfgang Goethe Univ. of Frankfurt am Main {Universität Frankfurt am Main / Universitas Francofurtensis ad Moenum} (1972-2011).

Doctorate, Universität des Saarlandes {Universitas Saraviensis} (adviser: Günter Hotz) (1967)

 

`Darstellbarkeit von sprachen durch freie assoziative systeme' {Representability of languages ​​by free associative systems}, 1967.

`Zufälligkeit und wahrscheinlichkeit: eine algorithmische begründung der wahrscheinlichkeitstheorie' {Randomness and probability: an algorithmic foundation for probability theory}, 1971.

`A unified approach to the definition of random sequences', 1971.

`Optimal enumerations and optimal Gödel numberings', 1971, 1974.

`Process complexity and effective random tests', 1972, 1973.

`Rekursive funktionen und ihre komplexität' {Recursive functions and their complexity}, 1974.

 `Zwei lineare untere schranken für die komplexität Boolescher funktionen' {Two linear lower bounds for the complexity of Boolean functions}, 1974.

`A survey of the theory of random sequences', 1977. 

`A 3n lower bound on the network complexity of Boolean functions', 1980.

`A Gödel theorem on network complexity lower bounds', 1986.

`An optimal sorting algorithm for mesh connected computers', 1986. (with A. Shamir)

`Polynomial time algorithms for finding integer relations among real numbers', 1986, 1989. (with J. T. Håstad, Bettina Just née Helfrich, J. C. Lagarias)

`A more efficient algorithm for lattice basis reduction', 1986, 1988.

`A hierarchy of polynomial time lattice basis reduction algorithms', 1986, 1987.

`Efficient signature generation by smart cards', 1989, 1991.

`Factoring integers and computing discrete logarithms via Diophantine approximation', 1991, 1993.

`Lattice basis reduction: improved practical algorithms and solving subset sum problems', 1991, 1994. (with M. Euchner)

`Block reduced lattice bases and successive minima', 1994.

`Segment-LLL-reduction of lattice bases', 2001. (with Henrik Koy)

`Segment- and Strong-segment LLL-reduction of lattice bases', 2002. (with Henrik Koy)

`Fast LLL-type lattice reduction', 2006.

`Progress on LLL and lattice reduction', 2009.

`Accelerated slide- and LLL-reduction', 2011.

`Factoring integers by CVP and SVP algorithms', 2013, 2020.

`Fast factoring integers by SVP algorithms', 2021.

Necrology: A. A. Muchnik

Necrology:

A. A. Muchnik [Albert Abramovich] / Альберт Абрамович Мучник
(2 Jan. 1934 - 14 Feb. 2019)

A. A. Muchnik: 

`Неразрешимость проблемы сводимости теории алгоритмов' {On the unsolvability of the problem of reducibility in the theory of algorithms}, communicated, Moscow mathematical society; read, 16 Oct. 1956; Доклады Академии наук СССР {Doklady akademii nauk SSSR / Proceedings of the USSR academy of sciences} (N. S.), 1956.

``Решение проблемы сводимости Поста и некоторых других проблем теории алгоритмов' {Solution of the Post reducibility problem and some other problems in the theory of algorithms}', received, 19 Feb. 1957, Труды Московского математического общества {Proceedings of the Moscow mathematical society}, 1958.

"I do not know if you have heard that `Post's problem', whether there are degrees of unsolvability among problems of the form (\exists y) \phi (y,x), where \phi is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father)."
-- Letter from K. Gödel to J. von Neumann, 20 Mar. 1956 (discovered in the Nachlass of von Neumann, 1988; no reply is known to exist, and von Neumann died on 8 Feb. 1957).

Richard M. Friedberg: `Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944)', communicated by K. Gödel, 11 Dec. 1956, Proceedings of the US National academy of sciences, 1957.

N. B.: Richard M. Friedberg [Michael] (b. 8 Oct. 1935) is a student of T.-D. Lee and Professor Emeritus of Physics at Barnard College and at Columbia University (1968-2003). He is the author of `An Adventurer's guide to Number theory', 1968. His father, Charles K. Friedberg [Kaye] (14 Sep. 1905 - 14 Jul.1972), was the author of `Diseases of the Heart', W. B. Saunders, 1949, 1956, 1966. The books of both father and son are with me.

Indu Satija: I; II