Necrology: C. A. R. Hoare

Necrology:

C. A. R. Hoare [Charles Antony Richard]

(11 Jan. 1934 [Colombo, Ceylon] - 5 Mar. 2026 [Cambridge, England])

no doctorate. 

student of John R. Lucas.

Professor of computation, Programming research division, Computing laboratory, Univ. of Oxford, 1977-1999.

husband of Jill Pym. 

 

Home page

`Hoare's interest in computing was awakened in the early 1950s, when he studied philosophy (together with Latin and Greek) at the Univ. of Oxford, under the tutelage of John R. Lucas. He was fascinated by the power of mathematical logic as an explanation of the apparent certainty of mathematical truth.'  

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.

The last lecture of John E. Hopcroft

Today is the last lecture of CS4850*. Lecturing to an empty classroom is nowhere near as satisfying as lecturing to 70 students in person. I know that listening to the lectures must also be nowhere near as valuable or interesting as going to a lecture, but it was the best we could do.

I was looking forward to this class as it was the last class I would teach in my career. I had hoped to get to know you all better but unfortunately, these circumstances interfered. I hope you have a successful time as you find what you really enjoy doing.

As soon as we grade the last homework we will post the grades.

Best,
John.

---

* Mathematical foundations for the information age

Location: Online
Lecture: MWF 1:25pm - 2:15pm
Instructor: John Hopcroft
Office Hours: By appointment

 

Lecture 11,  29 Apr.     Topic: Electrical Networks

 

===

John E. Hopcroft and his students at the 70th birthday conference, Oct. 2009:

Back row left to right: Alfred V. Aho, Richard J. Cole, Chandrajit Bajaj, John E. Hopcroft, Ravindran Kannan, Zvi Galil, Steven Fortune, Robert E. Tarjan, Gordon Wilfong. Allan Borodin.

Front row left to right: Laura Wang, Yookyung Jo, Daniela Rus, Kristen Summers, Sucheta Soundarajan, John Johnstone, Baining Guo, Gilles Brassard.

===

 

John E. Hopcroft [Edward]:
Idem, J. D. Ullman: `Introduction to Automata theory, Languages, and Computation', Addison-Wesley publishing company, Inc., 1979 (revision of `Formal languages and their relation to Automata', 1969).
A. V. Aho, Idem, J. D. Ullman: `The design and analysis of Computer Algorithms', Addison-Wesley publishing company, Inc., 1974.
A. V. Aho, Idem, J. D. Ullman: `Data structures and Algorithms', Addison-Wesley publishing company, Inc., 1983.

 

Idem, R. Kannan: `Foundations of Data science', Cambridge univ. press, Mar. 2020.

 

---

 

Photographs: N. Foster; Cornell Univ., Ithaca. 

Further keywords and labels: Hopcroft, J. E.; Asymptotic analysis of algorithms; Synthesis and analysis of algorithms; Algorithmics; Computation; Theory of computation; Automata; Languages; Concrete mathematics; Machine intelligence; Didactics and pedagogy; Mathematical exposition.

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