Yefim Dinitz (Russian: Ефим Абрамович Диниц,[2] Hebrew: יפים דיניץ) is a Soviet and Israeli computer scientist associated with the Moscow school of polynomial-time algorithms.
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.
[9][11] 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.
[6][13] In 1970, Dinitz, Mikhail Kronrod, Arlazarov, and Faradjev published the Boolean matrix multiplication algorithm that would make them famous as the "Four Russians".
[16][17] 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.
[6][4][10][16] 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".