Witold Lipski

Witold Lipski Jr. (July 13, 1949 – May 30, 1985) was a Polish computer scientist (habilitation in computer science), and an author of the books Combinatorics for Programmers (two editions) and (jointly with Victor W. Marek) Combinatorial analysis.

Witold Lipski Jr.
Witold Lipski autoportrait
Born	July 13, 1949 Warsaw, Poland
Died	May 30, 1985(1985-05-30) (aged 35) Nantes, France.
Nationality	Polish
Alma mater	Polish Academy of Sciences (Habilitation) Polish Academy of Sciences (PhD) Warsaw Technical University (BE/ME)
Known for	combinatorics, incomplete information, VLSI, Witold Lipski Prize
Scientific career
Fields	Computer Science Databases Combinatorics VLSI Graph Theory Logic Computational Geometry
Institutions	Polish Academy of Sciences University of Illinois at Urbana–Champaign University of Paris
Doctoral advisor	Wiktor Marek
Doctoral students	Tomasz Imieliński Zbigniew Michalewicz

Lipski and his PhD student Tomasz Imieliński worked on the foundations of the theory of incomplete information in relational databases.

Life

Lipski was born in Warsaw. He graduated from the Program of Fundamental Problems of Technology, at the Warsaw Technical University. He received a PhD in computer science at the Computational Center (later: Institute for Computer Science) of the Polish Academy of Sciences, under the supervision of Victor W. Marek. Lipski's dissertation was on the topic of information storage and retrieval systems and titled 'Combinatorial Aspects of Information Retrieval'.^[1] 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'. Their results were published from 1978 through 1985.^[2][3][4][5] This produced a fundamental concept later known as Imieliński–Lipski algebras.^[6][7][8]

With Imieliński, Lipski studied the semantics of relational databases. These investigations were based on the theory of cylindric algebras, a topic studied within universal algebra. According to Jan Van den Bussche,^[9] the first people from the database community to recognize the connection between Edgar Codd's relational algebra and Alfred Tarski's cylindric algebras were Lipski and 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 published in 1984.^[10]

Lipski contributed to research on algorithm analysis, discovering a number of efficient algorithms applicable to the analysis of VLSI devices (with Franco P. Preparata),^[11] time-sharing in database implementations (with Christos Papadimitriou),^[12] and computational geometry as applied to shape recognition (again with Preparata).^[13]

Lipski wrote the combinatorial algorithms textbook Kombinatoryka dla Programistow (Combinatorics for Programmers), which was published in two editions (one posthumous) and was translated into Russian.

Jointly with Marek, Lipski published a monograph on combinatorial analysis.

Personal life

Lipski's father was economist and politician Witold Lipski (1925–1998) [pl].

He had two children: Kasia (an endocrinologist) and Witold (a neuroscientist).

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

The Witold Lipski Award is the most prestigious award for young computer scientists in Poland. 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.

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 administered by the (Polish) Foundation for Computer Science Research,^[14] in cooperation with Polish Chapter of the Association for Computing Machinery, and the Polish Computer Science Society [pl].

Starting in 2024, the Kosciuszko Foundation has handed over the role of organizing the award to the research and development center IDEAS NCBR ^[15] in Warsaw. The official competition website is now hosted at: https://nagrodalipskiego.ideas-ncbr.pl/

See also

• Null (SQL)