Friday, April 03, 2009

Guest Blog by Clyde Kruskal on Jack Schwartz

(Guest Blog by Clyde Kruskal.)
Last week I attended the memorial for one of my three advisors, Jacob T. Schwartz, who passed away in the beginning of March. He was a Mathematician and Computer Scientist with enormous intellect and accomplishments. I suspect he is not as well known in the Complexity Community as he deserves. Here I discuss only some of his work. Next week I will talk a little about the memorial itself.

Jack was a member of both the National Academy of Sciences and the National Academy of Engineering. He had a wide range of interests, and switched fields every few years. Whenever he worked in a field, it seems that his goal was to accomplish something large. One trick of being his student was to finish fast enough before he switched fields. For my thesis in Parallel Processing, I did not actually succeed in doing so, but Jack created a large project with plenty of researchers, so there was still a rich enviroment for me. His seminal paper on Ultracomputers was the basis for the project.

Jack is probably best known for his classic three volume set, co-authored with Dunford, on Linear Operators, which won the Leroy T. Steele Prize for Mathematical Exposition.

He developed the SETL programming language, which is based on the concept that, since set theory is a good way to describe mathematics, it should also be a good way to write programs. It never really caught on but was influential in the field of computer languages and compilers. Python has its roots partially in SETL. The first ADA compiler was written in SETL. Here is an example of a SETL program for topological sort taken from Schwartz's website:

proc top_sort1(G,nodes);  top sort proc, rec form
  return if exists n in nodes | n notin range(G) then
      [n] + top_sort1(G lessf n, nodes less n) else [] end if;
end top_sort1;

A powerful optimizer is needed for such a high level language, and much effort went into this. GNU SETL is available. If you spend enough time in New York, eventually you will see four strong moving men twisting and turning a baby grand piano up four flights of narrow staircases. Figuring how to do this so that the piano fits is a computationally difficult task (The Piano Movers Problem). Jack co-authored a series of papers with Micha Shirir on this topic. This seems to be his most cited body of work in Computer Science.

Jack also worked outside of Math and Computer Science: He wrote a two volume set in Economics, and at the end of his life he was actively working in Biology.

Schwartz's [Wikipedia page] lists his interests to include: theory of linear operators, von Neumann algebras, quantum field theory, time-sharing, parallel computing, programming language design and implementation, robotics, set-theoretic approaches in computational logic, proof and program verification systems; multimedia authoring tools; experimental studies of visual perception; multimedia and other high-level software techniques for analysis and visualization of bioinformatic data.


  1. Don't forget the Schwartz-Zippel-(De Millo-Lipton) lemma, which is named after him.

  2. Is he also of "Cauchy-Schwartz"?

  3. No, that's Cauchy-Schwarz (note the different spelling), the second author being Hermann Amandus Schwarz (1843-1921).

  4. Dear Scott, While I am able more not-avoids says him more explicitly beyond condemnation of exemption or any another forward additional claim and on us this toward the present of past or future truly My Family (AND I) We the US (AM) a family. Seal it please it signs it prints recalls that writes it and changes it through the globe. :) This is not a smile and a wink. :)


  6. The Piano Movers Problem... seems to be his most cited body of work in Computer Science.

    I am a bit surprised since this is the Complexity Blog that Clyde didn't highlight the Schwartz-Zippel Lemma for polynomial identity testing as the first commenter has done. (Google Scholar does not seem to even index the 1980 J. ACM article in which Schwartz's proof of the lemma appeared but the ACM digital library lists 138 references for it.) Schwartz;s paper may not be cited because many citations seem to refer to standard texts rather than the original papers.

    As work by Impagliazzo and Kabanets has shownm this is not only one of the first really useful RP algorithms, it is also likely to be one of the last standing.

  7. The GNU SETL site is down. See the old site at