Phokion G. Kolaitis' Primitive Home Page

Updated Web Page

CHAPTER

On the Expressive Power of Logics on Finite Models (draft - to appear as a chapter in a volume on "Finite Model Theory and its Applications", to be published by Springer in the EATCS Series: Texts in Theoretical Computer Science) .

SOME SELECTED PAPERS:

Implicit definability on finite structures and unambiguous computations - in LICS 90) .

Infinitary Logics and 0-1 Laws (with M.Y. Vardi) - - in I&C 1992) .

Logical Definability of NP-Optimization Problems (with M.N. Thakur) - - in I&C 1994) .

Approximation properties of NP minimization classes (with M.N. Thakur) - in JCSS 1995) .

Integer Programming as a Framework for Optimization and Approximability (with I. Barland and M.N. Thakur - in JCSS 98) .

First-order logic vs. fixed-point logic in finite set theory (with A. Atserias - in LICS 1999) .

0-1 laws for fragments of existential second-order logic: a survey (with M.Y. Vardi - invited paper in MFCS 2000).

Conjunctive query containment and constraint satisfaction (with M.Y. Vardi - in JCSS 2000).

A game-theoretic approach to constraint satisfaction (with M.Y. Vardi - in AAAI 2000).

Existential second-order logic over graphs: charting the tractability frontier (with G. Gottlob and T. Schwentick - in FOCS 2000).

Phase transitions in PP-complete satisfiability problems (with D. Bailey and V. Dalmau - in IJCAI 2001) .

The complexity of minimal satisfiability problems (with L.M. Kirousis- to appear in Information and Computation; earlier version in STACS 2001) .

A dichotomy in the complexity of propositional circumscription (with L.M. Kirousis- in LICS 2001) .

On the complexity of model checking and inference in minimal models (with L.M. Kirousis- invited paper in LPNMR 2001) .

In search for a phase transition for the AC-Matching problem (with T. Raffill - to appear in CP 2001) .

On the complexity of existential pebble games (with J. Panttaja - full version of CSL 2003 paper) .

TALKS AND SHORT COURSES:

Tutorial on Constraint Satisfaction, Complexity, and Logic -- Logic Coloquium 2005, July 2005 (postscript slides) .

Inductive Definability and Finite-Variable Logics: From Logic to Computer Science, PLS 2005 - Invited Talk dedicated to Yiannis N. Moschovakis, July 2005 (powerpoint slides) .

Schema Mappings, Data Exchange, and Metadata Management - PODS 2005 Invited Talk, June 2005 (powerpoint slides - large file) .

On Preservation under Homomorphisms in the Finite - Logic Colloquium, UC Berkeley, April 2004 (postscript slides -updated May 2005) .

Constraint Satisfaction, Complexity, and Logic -- Distinguished Lecture Series Talk, University of Toronto, November 2003 (postscript slides) .

Data Exchange, Talk at the Database Seminar, University of Toronto, November 2003 (postscript slides) .

Constraint Satisfaction, Databases, and Logic -- Invited Talk at IJCAI 2003, August 2003 (postscript slides) .

Course on Constraint Satisfaction, Complexity, and Logic -- 2003 Barbados Workshop on Computational Complexity (expanded version of NASSLLI 2002 course - postscript slides) .

Constraint Satisfaction, Finite-Variable Logics, and Bounded Treewidth -- VIG Conference at UCLA in honor of Y.N. Moschovakis' 65th Birthday, January 2003 (postscript slides) .

Course on Constraint Satisfaction, Complexity, and Logic -- NASSLLI 2002 (postscript slides) .

Course on Combinatorial Games in Finite Model Theory -- ESSLLI 2001 (postscript slides) .

In search of a phase transition in the AC-matching problem -- CP 2001 (powerpoint slides) .

Phase transitions in PP-complete satisfiability problems -- IJCAI 2001 (powerpoint slides) .

Phase transitions in PP-complete satisfiability problems -- expanded talk, November 2001 (powerpoint slides) .

Model checking and inference in minimal models -- LPNMR 2001 (postscript slides) .

OTHER LINKS:

A recent picture: Picture 2004

My "official" UCSC web page with a 1988 picture as a younger man (a study on the effects of the passage of time): "official" web page.

Another picture from the distant past: Days of '78 in the Greek Navy.

Curriculum Vitae: CV.

IDM '01 Grant Report: IDM '01.

IDM '02 Grant Report: IDM '02.

IDM '03 Grant Report: IDM '03.

PODS 2002 Call for Papers: PODS 2002 CFP.

PODS 2002 Paper Submission Instructions: PODS 2002 CFP.

First North American Summer School on Logic, Language, and Information: NASSLLI 2002.