Phokion Kolaitis, professor of computer science at UCSC's Baskin School of Engineering, published a paper in 1998 that has now been recognized as a major influence in the field of database systems. The paper earned Kolaitis the Alberto O. Mendelzon Test-of-Time Award given for the first time this year by the Association for Computing Machinery (ACM) Symposium on Principles of Database Systems (PODS).
ACM PODS is the premier international conference on database theory. The symposium's award committee recognized two papers from 1998 as having "the most impact (in terms of research, methodology, or transfer to practice) over the intervening decade," and selected them as the 2008 award winners.
The paper by Kolaitis, coauthored with Moshe Vardi and published in the Proceeedings of PODS 1998, is titled "Conjunctive-query containment and constraint satisfaction." The paper relates two important problems in the areas of databases and artificial intelligence and provides a deep complexity analysis, according to the award committee's citation. (The other paper chosen for the award is "Complexity of answering queries using materialized views," by Serge Abiteboul and Oliver Duschka.)
Currently on leave of absence from UCSC, Kolaitis is at the IBM Almaden Research Center in San Jose, where he is the senior manager of the Computer Science Principles and Methodologies Department. His research interests include logic in computer science, database theory, and computational complexity.
A Fellow of the ACM, Kolaitis has received several IBM research awards and has held a Guggenheim Fellowship. He earned a diploma in mathematics at the University of Athens and M.A. and Ph.D. degrees in mathematics at UCLA. He joined the UCSC faculty in 1988.
