# Yefim Dinitz

Yefim Dinitz (Russian: Ефим Абрамович Диниц, Hebrew: יפים דיניץ) is a Soviet and Israeli computer scientist associated with the Moscow school of polynomial-time algorithms. He invented Dinic's algorithm for computing maximal flow, and he was one of the inventors of the Four Russians' algorithm for multiplying Boolean or mod 2 matrices.$^{:243,250}$

## Education and early work in the Adelson-Velsky group

Dinitz studied for a master's degree in Georgy Adelson-Velsky's group at Moscow State University. In 1969, Adelson-Velsky started a seminar on algorithms, which his students and others close to him would later describe as "the centre of scientific activity in polynomial-time algorithmics in Moscow". It was an exercise in "Adel'son-Vel'sky's Algorithms class", according to Dinitz, that led to the development of Dinic's algorithm in 1969. Looking back, Dinitz and his classmates would write that the design of the algorithm reflected the atmosphere of Adelson-Velsky's group. In Dinitz's words:
   We, Adel'son-Vel'sky's students, absorbed the whole paradigm of the Soviet computing school from his lectures. This paradigm consisted of eagerness to develop economical algorithms based on the deep investigation of a problem and on the use of smart data structure maintenance and amortized running time analysis as necessary components. … Hence, it was not surprising that my network flow algorithm, invented in January 1969, improved the Ford&Fulkerson algorithm by using and maintaining a layered network data structure and employing a delicate amortized analysis of the running time.
Dinitz published the algorithm in 1970.
In early 1969, Dinitz was also working on the assignment problem with his classmate Mikhail Kronrod, contributing to the body of work in which "the search for faster assignment algorithms began in earnest". The algorithm Dinitz and Kronrod published later that year could solve the assignment problem for n-vertex graphs in O(n$^3$) steps.
During their time in Adelson-Velsky's algorithms seminar, Dinitz and Kronrod crossed paths with Vladimir Arlazarov and Igor Faradjev—two young mathematicians working in the Mathematical Laboratory at ITEP. The lab was directed, until a political incident in 1968–1969, by Adelson-Velsky's academic sibling and longtime collaborator Aleksandr Kronrod. In 1970, Dinitz, Mikhail Kronrod, Arlazarov, and Faradjev published the Boolean matrix multiplication algorithm that would make them famous as the "Four Russians".

## Work in Moscow after the Adelson-Velsky group

Adelson-Velsky had also signed the 1968 letter that led to Aleksandr Kronrod's 1969 dismissal from ITEP. In 1970, the Faculty of Mechanics and Mathematics graduated Adelson-Velsky's whole student group, and Adelson-Velsky was banned from teaching at Moscow State University. However, Dinitz kept working on flow algorithms. He wrote a Moscow State University Ph.D. thesis on commodity flow problems, which he submitted in 1972. He developed the idea of capacity scaling independently of Edmonds and Karp, who had just introduced it in the West, and he used it to invent one of the first polynomial-time algorithms for the minimum-cost flow problem.
Dinitz also stayed in touch with his classmate Aleksandr Karzanov, publishing a paper on the minimum-cost flow problem with him in 1974. In 1975, Dinitz and Karzanov joined Adelson-Velsky in publishing a book on network flow algorithms, which "describe[d] many major results … that were independently discovered later (and in some cases much later) in the West".

## Publicity in the West

In 1974, Shimon Even and his graduate student Alon Itai at the Technion got curious about Dinitz's maximal flow algorithm, as well as a network flow algorithm that Karzanov had published around the same time. Dinitz's description of the algorithm was very compressed, due to journal page limits, but Even and Itai managed to decipher most of it, thanks in part to Karzanov's explicit explanation of a concept that was implicit in Dinitz's paper. After filling the last gap with a new technique of their own, Even and Itai had a working version of Dinitz's algorithm, which Even publicized in talks at many Western universities.
Dinitz's name was transliterated as "E. A. Dinic" in the English translation of his paper, so Even and Itai's version of his algorithm became known as Dinic's algorithm in the West, and his name was "rendered incorrectly as [dinik] instead of [dinits]" in that context.

## Later work at the Technion and Ben-Gurion University

In the 1990s, Even finally got a chance to learn the original version of Dinitz's algorithm from Dinitz himself. In 1992, Dinitz published a paper on the butterfly network with Even and two other Technion computer scientists, listing his affiliation as Ben-Gurion University. Dinitz would reportedly later recall that Even fought successfully for him to be hired as an associate professor at the Technion. He listed his affiliation as the Technion on a paper published in 1994, and he advised a Technion Ph.D. student in 1997. Dinitz joined the computer science department at Ben-Gurion University in 1998, and the department held a retirement celebration for him in 2019.
Due to his publications with Shlomo Moran and Shmuel Zaks in the late 1990s and the 2000s, Dinitz has an Erdős number of two.