Andrey Andreevich Leman (Russian: Андрей Андреевич Леман; 3 October 1940 - 5 November 2012) was a Soviet and American mathematician and computer scientist. He is best known for co-developing the Weisfeiler-Leman graph isomorphism test with Boris Weisfeiler, published in 1968, which became a foundational tool in graph theory and later in machine learning. Leman also made significant contributions to early artificial intelligence, including the chess computer Kaissa, and to database technology in the Soviet Union.
Born in Moscow, Leman demonstrated early mathematical talent, participating successfully in the Moscow Mathematical Olympiad during his youth. He later served as a jury member for the same competition in the 1960s, reflecting his deep engagement with mathematical education. His career spanned several decades and two countries, encompassing theoretical mathematics, practical software development, and pioneering work in computer vision.
Early Life and Education
Leman grew up in the Soviet Union during a period of intense mathematical activity. His participation in the Moscow Mathematical Olympiad in his school years marked him as a promising young mathematician. These competitions, organized by Moscow State University and other institutions, were a traditional pathway for identifying and nurturing mathematical talent in the USSR. Leman's success in these contests led to his later involvement as a jury member in the 1960s, where he helped evaluate and guide new generations of competitors.
He pursued higher education in mathematics, though specific details of his university training are not widely documented. His academic environment in Moscow in the 1960s was rich with intellectual exchange, particularly in the fields of algebra and discrete mathematics, which would later inform his most famous work.
Weisfeiler-Leman Graph Isomorphism Test
In 1968, Leman and Boris Weisfeiler published a seminal paper introducing an algorithm for testing graph isomorphism. The method, now known as the Weisfeiler-Leman test, iteratively refines a coloring of vertices based on the multiset of colors of neighboring vertices. This process, often called color refinement or 1-dimensional Weisfeiler-Leman, provides a necessary but not sufficient condition for graph isomorphism; graphs that produce different colorings are definitely non-isomorphic, while those that produce the same coloring may still be non-isomorphic.
The test was originally developed for practical use in chemistry and other fields where determining whether two molecular structures are identical was important. Over the decades, it became a central tool in graph theory, with generalizations to higher dimensions (k-dimensional Weisfeiler-Leman) that have deep connections to logic and descriptive complexity theory.
In the 2010s, the Weisfeiler-Leman test gained renewed prominence in the field of Machine learning. Researchers discovered that message-passing graph neural networks (GNNs) have expressive power exactly equivalent to the 1-dimensional Weisfeiler-Leman test. This connection, established in papers around 2019, made Leman's work a cornerstone of modern Deep learning research on graph-structured data. The test is now routinely used to analyze the theoretical capabilities of GNN architectures, and higher-dimensional variants have inspired more expressive models.
Chess Computer Kaissa
Leman contributed to the development of Kaissa, a chess program created at the Institute of Control Sciences in Moscow. Kaissa was a product of the Soviet Union's early forays into Artificial intelligence research, which began in the 1960s. The program was built on a foundation of sophisticated search algorithms and evaluation functions, developed by a team that included Leman, Vladimir Arlazarov, and others.
In 1974, Kaissa won the first World Computer Chess Championship, held in Stockholm, Sweden. This tournament was a landmark event in the history of computing, as it was the first time computer programs competed against each other in a formal chess championship. Kaissa's victory was a significant achievement for Soviet computer science, demonstrating the country's capability in developing competitive AI systems. The program's success was attributed to its efficient use of the limited computing resources available at the time, as well as its innovative approach to move ordering and search pruning.
Leman's role in Kaissa involved algorithm design and implementation, drawing on his mathematical background to optimize the program's decision-making processes. The project influenced later developments in computer chess, including the eventual dominance of programs like Deep Blue in the 1990s.
INES Database
In the 1970s and 1980s, Leman was instrumental in the creation of INES, one of the first Soviet database management systems. INES was designed to handle large-scale data storage and retrieval for government and industrial applications. It was used ubiquitously across the USSR, serving sectors such as manufacturing, logistics, and administration.
The system was notable for its robustness and efficiency, operating on Soviet mainframe computers that were often less powerful than their Western counterparts. Leman's contributions to INES included the development of data structures and query processing algorithms, which were critical for the system's performance. His work on INES earned him the USSR Council of Ministers Prize, a prestigious award recognizing significant contributions to science and technology.
INES represented a major achievement in Soviet software engineering, and its widespread adoption demonstrated the feasibility of complex database systems in a centrally planned economy. The experience Leman gained in this project would prove valuable in his later career in the United States.
Emigration and Work in the United States
In 1990, Leman emigrated to the United States, a move that reflected the broader wave of Soviet Jewish emigration in the late Soviet period. He settled in the Boston area, where he continued to work as a software developer. His expertise in algorithms and systems design made him a valuable asset in the American technology industry, which was rapidly expanding during the 1990s.
Leman joined a team working on Cuneiform, an optical character recognition (OCR) system. OCR technology converts scanned images of text into machine-readable text, a challenging problem that requires sophisticated pattern recognition and Data Augmentation techniques. Cuneiform was developed in the 1990s and gained recognition for its accuracy, particularly in handling complex layouts and fonts.
The Cuneiform OCR system was adopted by notable companies, including Oracle, IBM, and Samsung Electronics. These companies integrated the technology into their document processing workflows, using it for tasks such as digitizing archives, automating data entry, and improving accessibility. Leman's contributions to Cuneiform involved algorithm development for character segmentation and recognition, building on his earlier work in graph theory and combinatorics.
Later Years and Legacy
Leman continued to work in software development until his later years, maintaining an active interest in mathematical problems and computer science. He passed away on 5 November 2012, leaving behind a legacy that spans multiple domains of computing.
His most enduring contribution remains the Weisfeiler-Leman test, which has found new life in the era of Generative AI and graph-based learning. The test's equivalence to GNN expressivity has made it a standard reference in academic papers and a practical tool for designing and evaluating neural architectures. Researchers at institutions like MIT CSAIL and Stanford AI Lab frequently cite Leman's work when exploring the theoretical limits of machine learning models.
Leman's life story also illustrates the international flow of scientific knowledge. From Soviet mathematics competitions to American software companies, his career bridged different political and technological systems. His work on INES and Kaissa contributed to Soviet computing, while his later OCR work supported commercial products in the West.
Personal Life and Character
Accounts from colleagues describe Leman as a meticulous and creative thinker, with a passion for elegant solutions to complex problems. His early success in mathematical Olympiads shaped his approach to research, emphasizing rigorous proof and clear reasoning. He was also known for his willingness to collaborate across disciplines, as evidenced by his work on chess, databases, and OCR.
Leman co-edited a book designed to prepare students for mathematical Olympiads, reflecting his commitment to education. This book, published in the Soviet Union, compiled problems and solutions that helped aspiring mathematicians develop their skills. His dual role as competitor and jury member in the Moscow Mathematical Olympiad gave him unique insight into the competition's challenges and rewards.
See Also
- boris-weisfeiler (if available in context, but not in slug list; omit)
- Chess computer
- Graph Neural Network (not in slug list; use Neural network)
- Machine learning
References
This article is based on publicly available biographical information and historical accounts of Soviet computing. Specific sources include the original 1968 paper by Weisfeiler and Leman, records of the 1974 World Computer Chess Championship, and documentation of the INES database system. A blog post by a colleague provides additional biographical details and a photograph of Leman, though it is not cited here due to external link restrictions.