# Phokion G. Kolaitis

## contact information

Research Staff Member, Computer Science Principles & Methodologies

Almaden Research Center, San Jose, CA, USA

+14089271810

Almaden Research Center, San Jose, CA, USA

+14089271810

## links

### Professional Associations

**Professional Associations:**ACM | ACM SIGACT | ACM SIGLOG | ACM SIGMOD | American Association for the Advancement of Sciences | Association for Symbolic Logic

### more information

**More information:**Phokion Kolaitis' web page at UC Santa Cruz

**2009**

Laconic Schema Mappings: Computing the Core with SQL Queries

Balder ten Cate, Laura Chiticariu, Phokion G. Kolaitis, Wang Chiew Tan

Balder ten Cate, Laura Chiticariu, Phokion G. Kolaitis, Wang Chiew Tan

*Proceedings of the VLDB Endowment Journal**2*(*1*), 1006-1017, 2009
Reverse data exchange: coping with nulls

R Fagin, P G Kolaitis, L Popa, W C Tan

R Fagin, P G Kolaitis, L Popa, W C Tan

*Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*,*pp. 23--32*, 2009**2008**

Interactive Generation of Integrated Schemas

L. Chiticariu, P. G. Kolaitis, L. Popa

L. Chiticariu, P. G. Kolaitis, L. Popa

*SIGMOD*,*pp. 833--846*, 2008
Quasi-inverses of schema mappings

R Fagin, P G Kolaitis, L Popa, W C Tan

US Patent App. 11/970,057

R Fagin, P G Kolaitis, L Popa, W C Tan

*ACM Transactions on Database Systems (TODS)**33*(*2*), 11, ACM, 2008US Patent App. 11/970,057

**2005**

Composing schema mappings: Second-order dependencies to the rescue

R Fagin, P G Kolaitis, L Popa, W C Tan

R Fagin, P G Kolaitis, L Popa, W C Tan

*Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*,*pp. 994--1055*, ACM, 2005**Year Unknown**

Polynomial-time optimization, parallel approximation, and fixpoint logic

Structure in Complexity Theory ..., 2002 - ieeexplore.ieee.org

Structure in Complexity Theory ..., 2002 - ieeexplore.ieee.org

Exchange, Integration, and Consistency of Data: Report on the ARISE

NISR Workshop. SIGMOD ..., 2005

NISR Workshop. SIGMOD ..., 2005

On the complexity of model checking and inference in minimal models

Logic Programming and Nonmotonic Reasoning, 2001 - Springer

Logic Programming and Nonmotonic Reasoning, 2001 - Springer

On the boundedness problem for two-variable first-order logic

Logic in Computer Science, 1998. ..., 2002 - ieeexplore.ieee.org

Logic in Computer Science, 1998. ..., 2002 - ieeexplore.ieee.org

Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series)

2005 - portal.acm.org

2005 - portal.acm.org

On the complexity of counting the Hilbert basis of a linear Diophantine system

Logic for Programming and Automated ..., 1999 - Springer, 0

Logic for Programming and Automated ..., 1999 - Springer, 0

Exchange, integration, and consistency of data: Report on the ARISE/NISR workshop

ACM SIGMOD ..., 2005 - portal.acm.org

ACM SIGMOD ..., 2005 - portal.acm.org

Structure identification of Boolean relations and plain bases for co-clones

Journal of Computer and System ..., 2008 - Elsevier

Journal of Computer and System ..., 2008 - Elsevier

Implicit definability on finite structures and unambiguous computations (preliminary report)

5th Annual IEEE Symposium on Logic in Computer ..., 1990

5th Annual IEEE Symposium on Logic in Computer ..., 1990

Approximation properties of NP minimization problems

Journal of Computer and System Sciences, 1995, 0

Journal of Computer and System Sciences, 1995, 0

Unification algorithms cannot be combined in polynomial time

Automated Deduction—Cade-13, 1996 - Springer, 0

Automated Deduction—Cade-13, 1996 - Springer, 0

Integer programming as a framework for optimization and approximability

... ., Eleventh Annual IEEE ..., 2002 - ieeexplore.ieee.org

... ., Eleventh Annual IEEE ..., 2002 - ieeexplore.ieee.org

Phase transitions of PP-complete satisfiability problems

Discrete Applied Mathematics, 2007 - Elsevier

Discrete Applied Mathematics, 2007 - Elsevier

The complexity of counting problems in equational matching

Journal of Symbolic Computation, 1995 - Elsevier, 0

Journal of Symbolic Computation, 1995 - Elsevier, 0

Game quantification

Model-Theoretic Logics, 1985, 0

Model-Theoretic Logics, 1985, 0

On the expressive power of logics on finite models

Finite Model Theory and its Applications, 2007 - Springer

Finite Model Theory and its Applications, 2007 - Springer

Structural characterizations of schema-mapping languages

Communications of the ACM, 2010 - portal.acm.org

Communications of the ACM, 2010 - portal.acm.org

Asymptotic enumeration and a 0-1 law for m-clique free graphs

Bulletin, new series, of the ..., 1985 - cat.inist.fr, 0

Bulletin, new series, of the ..., 1985 - cat.inist.fr, 0

The containment problem for real conjunctive queries with inequalities

Proceedings of the twenty-fifth ACM ..., 2006 - portal.acm.org

Proceedings of the twenty-fifth ACM ..., 2006 - portal.acm.org

First-order logic vs. fixed-point logic in finite set theory

Logic in Computer Science, 1999. ..., 2002 - ieeexplore.ieee.org

Logic in Computer Science, 1999. ..., 2002 - ieeexplore.ieee.org

Computational complexity of simultaneous elementary matching problems

Journal of Automated Reasoning, 1999 - Springer, 0

Journal of Automated Reasoning, 1999 - Springer, 0

On the complexity of the decision problem for two-variable rst-order logic

Bulletin of Symbolic Logic, 1997, 0

Bulletin of Symbolic Logic, 1997, 0

On asymptotic probabilities of inductive queries and their decision problem

Logics of Programs, 1985 - Springer, 0

Logics of Programs, 1985 - Springer, 0

Repair checking in inconsistent databases: algorithms and complexity

... of the 12th International Conference on ..., 2009 - portal.acm.org

... of the 12th International Conference on ..., 2009 - portal.acm.org

0–1 Laws for Fragments of Existential Second-Order Logic: A Survey

Mathematical Foundations of Computer Science ..., 2000 - Springer

Mathematical Foundations of Computer Science ..., 2000 - Springer

Towards a theory of schema-mapping optimization

Proceedings of the twenty- ..., 2008 - portal.acm.org

Proceedings of the twenty- ..., 2008 - portal.acm.org

Implicit definability and infinitary logic in finite model theory

Automata, Languages and Programming, 1995 - Springer, 0

Automata, Languages and Programming, 1995 - Springer, 0

On the expressive power of variable-confined logics

... in Computer Science, 1996. LICS'96. ..., 2002 - ieeexplore.ieee.org

... in Computer Science, 1996. LICS'96. ..., 2002 - ieeexplore.ieee.org

Answering aggregate queries in data exchange

Proceedings of the twenty-seventh ACM ..., 2008 - portal.acm.org

Proceedings of the twenty-seventh ACM ..., 2008 - portal.acm.org

Constraint satisfaction, databases, and logic

INTERNATIONAL JOINT CONFERENCE ON ..., 2003 - Citeseer

INTERNATIONAL JOINT CONFERENCE ON ..., 2003 - Citeseer

0-1 laws for fragments of second-order logic: an overview

Logic from computer science (Proc. of Workshop, 1989), 1992, 0

Logic from computer science (Proc. of Workshop, 1989), 1992, 0

The connectivity of boolean satisfiability: Computational and structural dichotomies

Automata, Languages ..., 2006 - Springer

Automata, Languages ..., 2006 - Springer

A dichotomy in the complexity of propositional circumscription

Theory of Computing Systems, 2004 - Springer

Theory of Computing Systems, 2004 - Springer

Existential second-order logic over graphs: Charting the tractability frontier

Journal of the ACM (JACM), 2004 - portal.acm.org

Journal of the ACM (JACM), 2004 - portal.acm.org

Subtractive reductions and complete problems for counting complexity classes

Theoretical Computer Science, 2005 - Elsevier

Theoretical Computer Science, 2005 - Elsevier

0-1 laws for infinitary logics

... in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

... in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

On preservation under homomorphisms and unions of conjunctive queries

Journal of the ACM (JACM), 2006 - portal.acm.org

Journal of the ACM (JACM), 2006 - portal.acm.org

On the complexity of the containment problem for conjunctive queries with built-in predicates

Proceedings of the seventeenth ..., 1998 - portal.acm.org, 0

Proceedings of the seventeenth ..., 1998 - portal.acm.org, 0

Why not negation by xpoint

Proc. ACM Symp. on Principles of Database ..., 1988, 0

Proc. ACM Symp. on Principles of Database ..., 1988, 0

Implicit definability on finite structures and unambiguous computations

Logic in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

Logic in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

Almost everywhere equivalence of logics in finite model theory

Bulletin of Symbolic Logic, 1996 - JSTOR, 0

Bulletin of Symbolic Logic, 1996 - JSTOR, 0

K_l+1-Free Graphs: Asymptotic Structure and a 0-1 Law

Transactions of the American ..., 1987 - JSTOR, 0

Transactions of the American ..., 1987 - JSTOR, 0

A game-theoretic approach to constraint satisfaction

PROCEEDINGS OF THE NATIONAL ..., 2000 - aaai.org

PROCEEDINGS OF THE NATIONAL ..., 2000 - aaai.org

Fixpoint logic vs. infinitary logic in finite-model theory

... in Computer Science, 1992. LICS'92., ..., 2002 - ieeexplore.ieee.org

... in Computer Science, 1992. LICS'92., ..., 2002 - ieeexplore.ieee.org

The decision problem for the probabilities of higher-order properties

Proceedings of the nineteenth annual ACM ..., 1987 - portal.acm.org, 0

Proceedings of the nineteenth annual ACM ..., 1987 - portal.acm.org, 0

Constraint satisfaction, bounded treewidth, and finite-variable logics

Principles and Practice of Constraint ..., 2006 - Springer

Principles and Practice of Constraint ..., 2006 - Springer

0-1 Laws and decision problems for fragments of second-order logic* 1

Information and Computation, 1990 - Elsevier

Information and Computation, 1990 - Elsevier

Generalized quantifiers and pebble games on finite structures

Annals of Pure and Applied Logic, 1995 - Elsevier, 0

Annals of Pure and Applied Logic, 1995 - Elsevier, 0

Approximation properties of NP minimization classes

Journal of Computer and System Sciences, 1995 - Elsevier, 0

Journal of Computer and System Sciences, 1995 - Elsevier, 0

The expressive power of stratified logic programs

Information and Computation, 1991 - portal.acm.org, 0

Information and Computation, 1991 - portal.acm.org, 0

Schema mappings, data exchange, and metadata management

PROCEEDINGS OF THE ACM SIGACT SIGMOD ..., 2005 - Citeseer

PROCEEDINGS OF THE ACM SIGACT SIGMOD ..., 2005 - Citeseer

On the expressive power of Datalog: tools and a case study

Journal of Computer and System Sciences, 1995 - Elsevier, 0

Journal of Computer and System Sciences, 1995 - Elsevier, 0

On the decision problem for two-variable first-order logic

Bulletin of Symbolic Logic, 1997 - JSTOR, 0

Bulletin of Symbolic Logic, 1997 - JSTOR, 0

Conjunctive-query containment and constraint satisfaction

... of the seventeenth ACM SIGACT-SIGMOD- ..., 1998 - portal.acm.org, 0

... of the seventeenth ACM SIGACT-SIGMOD- ..., 1998 - portal.acm.org, 0