# Witold Lipski

Witold Lipski Jr. (July 13, 1949, in Warsaw, Poland – May 30, 1985, in Nantes, France) was a Polish computer scientist (habilitation in computer science), and an author of two books: Combinatorics for Programmers (two editions) and (jointly with Wiktor Marek Combinatorial analysis. Lipski, jointly with his PhD student, Tomasz Imieliński, created foundations of the theory of incomplete information in relational databases.

## Life

Lipski graduated from the Program of Fundamental Problems of Technology, at the Warsaw Technical University. He received a Ph.D. in computer science at the Computational Center (later: Institute for Computer Science) of the Polish Academy of Sciences, under supervision of Prof. Wiktor Marek. Lipski's dissertation was on the topic of information storage and retrieval systems and titled 'Combinatorial Aspects of Information Retrieval'. His habilitation was granted by the Institute of Computer Science of Polish Academy of Sciences. Lipski spent academic year 1979/1980 at the University of Illinois at Urbana–Champaign, and the last two years before his death, at the University of Paris.
Jointly with his doctoral student, Tomasz Imieliński, Lipski investigated foundations of treatment of 'Incomplete Information in Relational Databases'. The results of these investigations were published in the bibliographical items in the period of 1978 through 1985. This collaboration produced a fundamental concept that became later known as Imieliński–Lipski algebras.
Again, in collaboration with Imieliński, Lipski studied the semantical issues of relational databases. These investigations were based on the theory of cylindric algebras, a topic studied within universal algebra. According to Van den Bussche, the first people from the database community to recognize the connection between Codd's relational algebra and Tarski's cylindric algebras were Witold Lipski and Tomasz Imieliński, in a talk given at the very first edition of PODS (the ACM Symposium on Principles of Database Systems), in 1982. Their work, "The relational model of data and cylindric algebras" was later published in 1984.
Additionally, Lipski contributed to the research in the area of algorithm analysis, specifically by discovering a number of efficient algorithms applicable in the analysis of VLSI devices (collaboration with Franco P. Preparata), time-sharing in database implementations (collaboration with Christos Papadimitriou), computational geometry (as applied to shape recognition, again, in collaboration with Franco Preparata).
Lipski was an author of a book on combinatorial algorithms, Combinatorics for Programmers (Kombinatoryka dla Programistow, in Polish). This book has had two editions (one of these posthumous) and it was also translated in Russian. Additionally, jointly with Wiktor Marek, Lipski published a monograph on combinatorial analysis.

## Personal

Witold Lipski Jr. is survived by two children, Dr. Kasia Lipska, endocrinologist, and Dr. Witold Lipski, neuroscientist. The father of Witold Lipski Jr. was an economist and politician Witold Lipski Sr.
Lipski died in Nantes, France, after a battle with cancer. He is buried in Powązki Cemetery in Warsaw, Poland, (Location: C/39 (5/7)).

## Witold Lipski Award for Young Computer Scientists in Poland

The Witold Lipski Award is the most prestigious award for young Computer scientists in Poland. Many are inspired by the brilliant career of Witold Lipski whose life was cut short by a terminal illness. The award recognizes achievements in the field of theoretical and applied computer science. It was created by the initiative of a group of Polish computer scientists active outside of Poland and in Poland. The submissions for the award are limited to applicants with exceptional accomplishments, who are younger than 30, or who are younger than 32, in case that a candidate was on maternity/paternity leave. The award is administrated by the (Polish) Foundation for Computer Science Research, in cooperation with Polish Chapter of the Association for Computing Machinery, and the Polish Computer Science Society. Starting in 2024, the Kosciuszko Foundation has handed over the role of organizing the award to the research and development center IDEAS NCBR in Warsaw. The official competition website is now hosted at: https://nagrodalipskiego.ideas-ncbr.pl/