Computer Science and Technology in Israel, 1950–1980

Eli Shamir

Introduction

During the decade commencing 1990, Computer Science and Technology (CST) and its business applications emerged as the dominant force in the massive growth of the Israeli economy. Relatively, its pull in Israel has been far stronger than in other technologically developed countries. This shows up in several indicators: revenues, size and quality of manpower, number of start-ups, and of successful companies. On 27 November 2007, The Marker, a business paper, carried a headline revealing that three Israeli CST companies took the top three positions among 500 European companies engaged in the endeavor, through achieving the most rapid five-year growth.¹

Israel’s continued contribution to global CST is far out of proportion to its small size, and is equivalent to that of a nation of at least ten times the population. This is evidenced by the number of scientific publications in journals and presentations at corporate conferences. Five major international CST companies have opened research and development centers in Israel. In some sectors, Israel has been a ‘pocket empire’ right from the start: CST theory and foundations, randomness and computations, complexity hierarchy, cryptography, data and a transaction protection, logical verification of programs and designs, as well as several other related areas. Last but not least, Israelis have won three Turing Awards (the CST equivalent of the Nobel Prize) and many other prestigious prizes.

This article focuses on the initial period of CST, roughly 1950–1980. It was a period of fast, in fact quite amazing, growth. However, the major evolutionary CST expansion came after 1980 with the arrival of the PC and the internet. Here I give an objective description of the Israeli origins of CST, in part based on personal experience and involvement, primarily on the academic front. Much information about this story is also available at web pages, and can be accessed by topics, persons, prizes, institutions, etc.

The CST global scene, 1950–1980

After 1945, as the United States emerged as the leading world power, it underwent massive economic growth. American made computers became an engineering reality, and their potential caught the imagination of a few significant visionaries.

For many years, CST was basically a one country show: hardware, software and service were mostly of US origins. CST advances in other countries depended to a large extent on the strength of their connection with the US, which for its part imposed a selective embargo on exports of certain critical technologies.

Despite amazing advances in hardware (VLSI), peripherals, software and applications, the machines of that period were mainframes of various sizes, located and serviced at the computation centers of large organizations. Training of service personal was conducted by manufacturers and through specialized courses. This applied also to programming tools, the human machine and assembly languages. Higher programming languages were invented. For a considerable time, most software was written in COBOL for logistics, and in FORTRAN for ‘number crunching’ applications. Gradually, universities introduced ‘service courses’ in programming.

The science² itself grew under the influence of pressing issues: the nature and logic of computing and data-manipulation, hardware design and architecture, the human machine interface, languages and graphics, software engineering and various applications of Artificial Intelligence (AI).

At the cradle of the new science can be identified Electrical Engineering (EE), mathematical logic, numerical computational mathematics and business applications, epitomized by the IBM corporation. Bold universities jumped in to create independent CST (or CSE, ‘E’ for engineering) departments, and fully-fledged education projects in CST, from first to third degree levels. A prominent role in CST development was played by the research divisions of giant corporations, mainly the AT&T Bell Laboratories in New Jersey, the IBM Thomas J. Watson research center in New York, and several IBM scientific centers at other locations.

Geo-economic effects on computer science and technology in Israel, 1950–1980

In 1948, the population of the new state of Israel was ¾ million. By 1980, it had exceeded the 4 million mark. Though Israel is geographically quite small, nevertheless rapid, effective communications were, and remain, important in several sectors.

The logistic center of Israel in finance, business, light industry, and even Army logistics, is in the greater Tel Aviv area (Gush Dan). However, during 1950–1980, academic institutions were mostly outside: Tel-Aviv (TAU) and Bar Ilan (BIU) universities had just started growing and were far from their present-day sizes. Higher education colleges did not exist. The three other, older, academic institutions were at the periphery of Gush Dan.

The Hebrew University of Jerusalem (HUJI)³ is in the capital city, yet (even after 1967) it was at the periphery in numerous ways, not only geographically. In Haifa, the Technion for a long time was the unique single institute of technology. The Weizmann Research Institute in Rehovot is closer to Tel-Aviv, yet was quite detached from it in the pre-1980 period. This detachment had several effects:

1. Training of CST personnel, mainly for logistics, was carried out mostly near Tel-Aviv. The army, a heavy user, established its own school, ‘MAMRAM’.
2. At universities, the focus was on number crunching for scientific applications. At Weizmann, the department of applied mathematics launched into an ambitious construction program for its own computers.
3. The connections between academia and industry were meager, and unsatisfactory on both sides. Government and industry funding were very low (even relatively, compared to other sciences).
4. Misconceptions about the goal of CST academic education. Industry leaders were slow in grasping what they really needed: workers capable of learning and adjusting to swiftly changing technologies. Indeed, CST academic education in general should emphasize the profound nature and basic principles of CST, rather than current technologies.

Israeli academic institutions eventually found the most promising channel for engagement: the powerful attraction to CST in the US. This factor cannot be over-estimated. Even though Israeli sciences are heavily US-oriented, in CST the effect was (and still is) by far the strongest. Here was an exhilarating new science, centered in the richest country on earth. Young talent could quickly reach the frontiers of CST and embark on an impressive career. At the large research centers in the US, positions were available without the ‘tenure-track’ handicap at universities; in addition there were sabbaticals and summer posts. Clever students foresaw the opportunities (both in the US and back in Israel), registered at the leading US universities, and continued on to post-doc positions.

Moreover, the professional and social establishments, and the influx of US grant money from military and civil agencies to professors at Israeli universities, allowed them and their talented students to carry out CST research year-round, without heavy dependence on expensive laboratories (a severe handicap for the experimental sciences).

In the wake of the 1973 Arab-Israeli war, Israeli military procurement underwent a sharp shift, from mostly European to mostly US suppliers, enhanced by a large military aid budget. The high-tech CST component in this was and remains very prominent. Soon, US training and studies for young personnel from the Army and defense-oriented industries quickly increased. Prior to that period (and sometimes even after 1980), US policy was highly restricted, almost embargo-like. Thus, during most of the pre-1980 period that we are considering, the vital connections with the US CST centers went almost exclusively through the Israeli universities.

The growth of computer science and technology in academia and industry, 1950–1980

First generation computers were installed at universities after 1955. They enhanced numerical solution of models (equations, constraints) and designs in the physical and engineering sciences. These applications induced research in the mathematics of numerical techniques (e.g. finite element methods), and required proficiency in writing and running the resulting computer programs.

These ‘hands-on’ users usually took the decisions: which computers to install (or build), as well as the contents of the service courses (FORTRAN, Assembly Languages).

At another level, a strong push of theoretical CST research started very early on. Young Israeli faculty members from EE, mathematics, and logic, cultivated connections with colleagues (and with projects) at MIT, Princeton, and the Bell and IBM laboratories. They managed to acquire US research grants (such as the Office of Naval Research grant for ‘Applied Logic’ at HUJI), and attracted PhD students from these disciplines to work with them on a variety of fundamental CST issues: abstract machine models, ranging in complexity from simple finite automata to Turing machines, including formal grammars, pushdown machines, Petrie nets, and early neural nets. The logical nature of computing and the limits of computability were studied, including surprising undecidable task (the non-existence of desired algorithms). Other directions included early hierarchies of complexity, and algorithms for basic problems. A respectable part of the early Israeli work in CST found its way into the basic teaching courses and early text-books in CST.

At Weizmann, the applied math department launched an ambitious program for building its own computers. The WEIZAC design (1955–1960) used know-how from the von Neumann computer at Princeton. More advanced designs (by orders of magnitude), GOLEM⁴ I, and II, were built and used in 1960–1973. These achievements were properly acknowledged. Like similar designs at several universities abroad, they could not complete commercially with the (US) industrial manufacturers, their marketing methods,⁵ and the backup service they provided. Prominent CST figures received their early experience on these machines at Weizmann.

The growth process at CS academic departments was initiated and monitored by tenured faculty members from EE, mathematics and logic. There were no established, mature authorities in CST available to hire (even if one wanted to). The one policy which did work well was the hiring of the best from the pool of young Israelis who had done significant post-doc research at American universities or research centers. An initial batch (of 4 or more individuals) was hired, taking care to cover distinct sectors so that a balanced course-program could be offered. After that, a growth rate of one or two positions per year was maintained and small research teams emerged in a few areas. The newly-joined young faculty members quickly acquired a decisive role in the running of departments and in shaping their growth.

The Technion took the lead. Already in 1970 it boldly established a fully-fledged program, from BSc (plus diploma) up to MSc and PhD levels. Impressive sequences of courses were developed, based on lecture notes (from abroad or home-produced) and on early text books. Throughout (and, indeed, until today) the Technion has the largest CS department in every respect: size of student body, faculty, budget, and facilities. Few other departments (in particular EE) offer programs which contain many CST courses.

At HUJI, the CS program and department was initiated by a few pioneers from the math institute. It started cautiously, around 1970, with MSc studies (and a separate location for faculty offices). The full BSc degree started in 1979, and a decade later CS separated (amicably) from math, to become an independent institute—today it is the school of Engineering and CS.

At Weizmann (which has no undergraduate studies), the Feinberg Graduate School started the MSc and PhD programs in CS quite early, around 1970.

The four other universities (TAU, BIU, Ben-Gurion University (BGU) and Haifa) joined in as well after 1980, although some selected courses were offered earlier.

Impediments

Those found at HUJI were quite typical (and were also found at Harvard and other places). Skeptics and opponents wondered whether CS was a basic science⁶ or perhaps only a branch of EE? Other important questions were raised. Where to recruit such faculty members? Will students come? Will graduates find employment? What kind of education and courses should be provided (e.g. teach FORTRAN and COBOL at freshmen level or introduce modern programming languages)? Evidently, other science departments were worried, fearing the loss of good students and resources to the newcomers.

Defense and industry

Logistic uses dominated in the early generations of computers at the government agencies, army and large corporations. The professionals and users established an active association of information processing, Israel Association of Information Technology (ILA). The engineering-oriented applications took off well before 1960. The budding aircraft industry, and the weapons development authority, both operated by the Defense Ministry, developed a growing demand for computing power, know-how and personnel. By 1961, private enterprise stepped in to create a high-tech industry, primarily electronic oriented, relying on large defense orders and requirements, but also gradually increasing export and civilian products. ELRON was first, undergoing stages of proliferation and expansion, and soon assumed the form of a holding conglomerate which today fully or partly owns about 30 companies, in a variety of high-tech fields.

Around 1973, the abrupt transfer of US military equipment, aid, and technological ties, boosted local CST oriented industries.

Scitex corporation was a most notable ’civilian’ pioneer, developing computerized printing, textile design, colour-seperation and graphic programming.⁷

The mutual connections of academy with industry and Army increased in several ways—funding, joint projects and exchange of know-how.

A few selected units in the Army and Air Force and Intelligence Services employed exceptionally gifted youngsters with mathematics and CST talents, for the development of clever algorithms.

It is no surprise that these youngsters later occupied leading positions in academy and CST industry in Israel.

Israel’s contribution to computer science and technology

Computers are the most complex engineering products that human ingenuity has created. Chips with enormous numbers of transistors and connections constitute the brain of PCs and of large mainframes as well. Their design and verification rely on human ingenuity and on automated programming. Intel Corporation, a leading manufacturer, carries out much of the complex design in its Haifa development center, and part of the production in its Kiriat-Gat factory. An IBM research center was established in Israel in 1972. Microsoft, Google and others followed in due course.

The enormous capacity and the speed of computers has revolutionized all areas of human activity. The complex character of many natural phenomena and social structures has been revealed, ironically an opposite trend to the classical striving of science over centuries to arrive at a few basic, universal laws of nature.

Complexity themes emerged quite early in CS theory. An extreme form of complexity, namely computational undecidability, was shown by an Israeli team at HUJI (supported by a grant from the Office of Naval Research for research in ‘Applied Logic’) to bear on practical issues concerning the syntax of programming languages. The syntax was specified in the mid-1950s by ‘Bachus Naur Form’ (BNF, formal grammars of ‘context-free’ type). Don Knuth (Turing Award recipient, 1974) expressed surprise and frustration—after investing much effort, even during his honeymoon—upon learning that the issue of non-ambiguity of BNF, and the equivalence of two BNF grammars, are provably impossible to decide by a computer program (i.e. by a Turing machine).[2]

It was soon realized that tasks may be decidable/computable, but very complex, and in practice intractable. The first construction of the time-complexity hierarchy of computable functions is found in an (unpublished) report of Michael Rabin from 1960 [14], five years before the famous Hartmanis-Stearns paper [8] which led them to a Turing Award (1993).

Complexity hierarchies became the backbone of CS theory, the rib structure being provided by COOK-KARP reducibility maps between computation tasks. The Garey and Johnson book Computability and Intractability plunged into a vast morass of inter-reducibility between computation tasks from various domains. Even old hands were amazed to see the reductions in complexity of tasks, such as finding a feasible piano moving path, or anaphora resolution in natural languages (finding the correct matching of the various pronouns in a text).

The intuitive complexity of natural language understanding (or tasks like Machine Translation) was forcefully argued by the late Bar-Hillel [1], head of the ‘Applied Logic’ project at HUJI around 1960.

The logical steps to bridge from inherent complexity to feasible programs include randomized algorithms, goal relaxations, approximate solutions and more. Israeli scientists were very prominent in these areas. We skip details, jumping 20 years forward to (interactive and) Probabilistically Checkable Proofs (PCP). PCP theory (and its implications) has been considered the cutting edge of CS Theory during the last decade. Both old and young Israeli researchers are involved in the PCP development. One of the first triggers for this development was a famous email sent around in 1991 by Noam Nisan, showing an example of an interactive PCP for a notoriously hard computation task [11].

The topics of pseudo-random one-way functions, zero knowledge interactive proofs, and the wide area of modern cryptography (encryption, cryptanalysis, secure protocols) are closely related to complexity. Again, Israeli contributions, before and after 1980, are very conspicuous. The middle S in the RSA public key system, which gained wide use, stands for Adi Shamir.

Several start-ups were formed in the area of data and protocols security. The best known, with ongoing success, is Check Point Corporation and its firewall line of products. Its creators (headed by Gil Schweid, CEO for 25 years) combined Israeli army experience and needs with the innovative ingenuity of Israeli science.

Specification and verification of software and hardware

The Israeli contribution is very prominent in the development of logical, graphical and algorithmic tools for these crucial tasks. Amir Pnueli won the Turing Award for his contribution (1996, see next section). He worked and published with distinguished collaborators (Zohar Manna and David Harel), and his students promoted this area of research in several Israeli universities, at INTEL and IBM research development centers, and in high-tech industry [3, 12, 13].

Prizes and awards

The excellence of Israelis in CST has been acknowledged through prestigious international and local prizes.⁸ Most of the prize-winners did much of their award-winning work in the pre-1980 period, and have continued to pursue research since then.

The A.M. Turing Award

The A.M. Turing Award has been given by the ACM every year since 1966. It was awarded to Michael Rabin in 1976, Amir Pnueli in 1996, and Adi Shamir in 2002. The Nevanlinna Prize for CS excellence is awarded every four years by the International Mathematical Union at its congress. Avi Widgerson won it in 1992. In CST these prizes are considred the equivalent of the Nobel. All four Israelis have won several other prizes and honors, and have parallel appointments in the most prestigious academic institutions in the US.

Israeli prizes

Two Israeli national prizes, the Rothschild Prize and recently established Emmet Prize, are awarded annually, rotating between areas (each area recurs every 3 or 4 years). The area of CST was added around 1995.

The Israel Prize (commencing in 1956) has been won by Joel Rocah, Physics, 1958; Chaim Pekeris, Mathematics, 1982; Jacob Ziv, Engineering, 1993; Michael Rabin, CST, 1995, Amir Pnueli, CST, 2000; David Harel, CST, 2005; and Noga Alon, Adi Shamir, Mathematics, 2008. Also in 2008 the RESPONSA project, a full-text retrieval data-base of Jewish scholarship, was endowed the Israeli prize as a specific project, with Aviezri Fraenkel and Jacob Choueka as its chief scientific contributors.

The (late) illustrious physicist Joel Rocah was considered a genius in numerical calculations and programming on early generation machines, including WEIZAC and GOLEM, especially in calculating complex atomic spectral lines. Jacob Ziv, a professor in EE at Technion, is co-author of the famous Ziv-Lempel text-compression algorithm. He chaired the Israel Academy of Sciences and gave continued support to CST development in academia and industry. Noga Alon and Micha Sharir, both distinguished mathematicians in TAU, made significant contributions to algorithmic design and analysis geometry, combinatorics and other fields. Sharir won the Emmet Prize in 2007. David Harel, has authored successful popular books on algorithmics and CST, in addition to making very important CST contributions. [7]

The Rothschild Prize (commencing in 1959) has been won by Joel Rocah, Physics, 1961; Chaim Pekeris, Mathematics, 1965; Miron Melman, Shmuel Ruchman and Zvi Riesel, Engineering, 1969; Michael Rabin, Mathematics, 1973; Achi Brandt, Mathematics, 1990; Adi Shamir, Mathematics, 1994; and Jacob Ziv, Engineering, 2002.

Other prizes

The Gödel Prize was inaugurated in 1998; the annual ceremony alternates between the US STOC conference and the European ICALP conference. It is awarded to the best journal article published in the previous year. It is remarkable that 10 out of the 40 winning co-authors are Israelis. It continues the tradition, in the pre-1980 period, of an exceptionally high Israeli presence in leading CST conferences—STOC, FOCS, SODA, RANDOM, CRYPTO, EUROCRYPTO and others.

Niv Ahituv, of TAU Business and Management School, won a special ILA Association Prize in 2004, for scientific and academic excellence in promoting information technology. Uziah Galil and Effi Arazy won several prizes and honors for their industrial achievements.

IBM established the Raviv Memorial Post-Doctoral Fellowship in honor of the late Joe (Joseph) Raviv, a prominent CST scientist, who founded the IBM research center in Israel in 1972 and was its director for many years (in fact, almost until his untimely death in 2001 as a result of an accident). Raviv helped in promoting several CST projects in Israel, including the School of Engineering and CS at HUJI.

Institutional growth

The leaders of the Technion pioneering CST program⁹ are: Michael Yoeli, the late Pinchas Naor, Jacob Katzenelson, Alan Reiter, Zvi Cochavy, Avraham Lempel, Israel Cederbaum, Azaria Paz, the late Shimon Even, and Avraham Ginzburg himself—with sweeping energy.

At HUJI, Michael Rabin and Eli Shamir led the growth of the CS Department (later Institute), which began as a part of the department of Mathematics (as stated in the citation of Rabin's Israel Prize, 1995). Both were already active in the Applied Logic project which the late Yehoshua Bar-Hillel started at HUJI in 1958. Bar-Hillel and the project attracted several research students from math (Haim Gaifman, Micha Perles, and Eli Shamir), and also from other areas, to research in CST. Eliezer Lozinski (who came from the Kiev cybernetic institute), Amnon Barak and Daniel Lehmann were appointed around 1980. ‘The big leap’ forward came with the appointment of Catriel Beeri, Danny Dolev, Nati Linial, Shmuel Peleg, Marc Snir (three of them were Eli Shamir’s PhD students), and somewhat later, Shuky Sagiv and Avi Widgerson. Very soon, the newly appointed researchers became leaders in the field. Daniel Braniss came from Argentina in 1975 to establish (and continues to be the leading expert in) the system group at the HUJI CS institute. For many years he was the leading authority in Israel on UNIX operating systems.

At Weizmann, CST developed in the applied math department, founded and chaired for many years by Haim Pekeris. During 1960–1970, the Golem project was central, involving Zvi Riesel, Shmuel Ruchman and Miron Milman (who won the 1969 Rothschild Prize) and others. In parallel, numerical methods and analysis were developed by Achi Brandt and his students, and by Pinchas Rabinovich. In the theoretical and algorithmic fields the leaders were Zohar Manna, Aviezri Fraenkel, Amir Pnueli and Shimon Even (Eli Shamir served as a consultant during 1970-82). ‘The big leap’ came around 1980, with the simultaneous appointment of Pnueli (back from TAU), Adi Shamir, David Harel and Shimon Ullman.

At TAU, in the pre-1980 period, the main activity was in two areas: numerical methods and applied mathematics at the school of sciences, and in parallel, information technology and logistics, at the business and management school, with Niv Ahituv as a leader. Boaz (Boris) Trachlenbrot came to Tel Aviv University from the Soviet Union in 1980, which giving a great boost to the field of logic and computation theory. [16] The ‘big leap’ came there around 1990, creating a large CS department in the school of exact sciences and also a smaller one in the school of engineering.

At BIU CS courses were for a long period offered by outside lecturers. CST was unable to achieve independant status because of opposition within the mathematics department. The ‘big leap’ at BIU, as well as at Haifa University and BGU, came after 1990, again as a result of hiring the best from the crop of youngsters who did their post-docs at American institutions.¹⁰

References

[1] Y. Bar-Hillel, Language and Information, Selected Essays, Addison-Wesley, 1964.

[2] ------, M. Perles and E. Shamir, ‘On Formal Properties of Simple Phrase Structure Grammars’ Z. Phonetics, Sprchwiss. Kommunication. 14, pp. 143-172, 1961.

[3] E. Clarke, D. Peled and O. Grumberg, Model Checking, MIT Press, 1998.

[4] S. Even, Algorithmic Combinatorics, MacMillan, 1974.

[5] ------, Graph Algorithms¸ Computer Science Press, 1979.

[6] M.R. Garey and D.S. Johnson, Computability and Intractability, W.H. Freedman, 1969.

[7] D. Harel, Algorithmics, the Spirit of Computing, Addison Wesley, 1987, 1992.

[8] J. Hartmanis and R.E. Stearns, ‘On the Computational Complexity of Algorithms’, Transactions of the American Mathematical Society, 117, pp. 285-305, 1965.

[9] S. Katz, ‘Berlin Roots… the Ethos of Pure Mathematics… at the Hebrew University’, Science in Context, 17, pp. 199-234, 2004.

[10] Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill, 1970.

[11] C. Lund, L. Fortnow, H. Karloff and N. Nisan, ‘Algebraic Methods for Interactive Proof Systems’, Journal of the ACM, 1992.

[12] Z. Manna, Mathematical Theory of Computation, McGraw-Hill, 1974.

[13] ------, and A. Pnueli, Temporal Verification of Reactive Systems, Springer, 1995.

[14] M.O. Rabin, ‘The Degree of Difficulty of Computing a Function and a Partial Order Recursive Sets’, Hebrew University, Applied Logic Branch, Report 2, 1960.

[15] ------, and D. Scott, ‘Finite Automata and their Decision Problems’, IBM, J. Res. 3, pp. 115-125, 1959.

[16] B.A. Trachtenbrot, Algorithms and Automatic Computing Machines, D.C. Heath, 1963 (Russian original, 1957).

Notes

Illustration credits

• 1 Source: Eli Shamir
• 2 Source: Wikimedia commons
• 3 Photo by Beny Shlevich, Source: http://www.flickr.com/photos/shlevich/ under license CC BY-SA 2.0
• 4 Source: Shlomo Marcus/Hebrew University
• 5 Copyright © 2005 David Monniaux
• 6 Source: Adi Shamir
• 7 Source: Shlomo Marcus/Hebrew University