Phokion G. Kolaitis

Phokion G. Kolaitis's AcademicInfluence.com Rankings

Phokion G. Kolaitis

Computer Science

#2448

World Rank

#2557

Historical Rank

Database

#1921

World Rank

#2016

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Phokion G. Kolaitis's Degrees

PhD Computer Science University of California, Berkeley

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Phokion G. Kolaitis Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Phokion G. Kolaitis ACM is a computer scientist who is currently a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.

(See a Problem?)

Phokion G. Kolaitis's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Data exchange: semantics and query answering (2003) (1446)
Conjunctive-query containment and constraint satisfaction (1998) (445)
On the Decision Problem for Two-Variable First-Order Logic (1997) (348)
Data exchange: getting to the core (2003) (317)
Schema mappings, data exchange, and metadata management (2005) (314)
Composing schema mappings: second-order dependencies to the rescue (2004) (294)
Finite Model Theory and Its Applications (2007) (202)
Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics (2002) (200)
Why not negation by fixpoint? (1988) (183)
On the expressive power of datalog: tools and a case study (1990) (168)
Infinitary Logics and 0-1 Laws (1992) (151)
Repair checking in inconsistent databases: algorithms and complexity (2009) (149)
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies (2006) (145)
Peer data exchange (2005) (143)
Generalized quantifiers and pebble games on finite structures (1992) (121)
Data exchange: getting to the core (2003) (118)
Quasi-inverses of schema mappings (2007) (104)
On the Unusual Effectiveness of Logic in Computer Science (2001) (103)
Hardness Of Approximations (1996) (101)
Approximation properties of NP minimization classes (1991) (101)
Logical Definability of NP Optimization Problems (1994) (95)
The decision problem for the probabilities of higher-order properties (1987) (95)
Designing and refining schema mappings via data examples (2011) (93)
Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar] (2008) (93)
Subtractive reductions and complete problems for counting complexity classes (2000) (92)
Towards a theory of schema-mapping optimization (2008) (85)
0-1 laws and decision problems for fragments of second-order logic (1988) (84)
Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series) (2005) (83)
Fixpoint logic vs. infinitary logic in finite-model theory (1992) (82)
Structural characterizations of schema-mapping languages (2009) (79)
On preservation under homomorphisms and unions of conjunctive queries (2004) (78)
The complexity of data exchange (2006) (76)
A Game-Theoretic Approach to Constraint Satisfaction (2000) (72)
Answering aggregate queries in data exchange (2008) (70)
Interactive generation of integrated schemas (2008) (68)
The Expressive Power of Stratified Programs (1991) (68)
The containment problem for <bi>Real</bi> conjunctive queries with inequalities (2006) (67)
Reverse data exchange: Coping with nulls (2009) (66)
Schema Mapping Evolution Through Composition and Inversion (2011) (64)
Implicit definability on finite structures and unambiguous computations (1990) (64)
Constraint Propagation as a Proof System (2004) (64)
Learning schema mappings (2012) (62)
Composing schema mappings: Second-order dependencies to the rescue (2005) (62)
Some computational aspects of circumscription (1988) (60)
Characterizing schema mappings via data examples (2011) (60)
On the Data Complexity of Consistent Query Answering (2012) (56)
The complexity of minimal satisfiability problems (2001) (53)
A dichotomy in the complexity of consistent query answering for queries with two atoms (2012) (53)
Almost Everywhere Equivalence of Logics in Finite Model Theory (1996) (51)
Structure identification of Boolean relations and plain bases for co-clones (2008) (51)
Laconic Schema Mappings: Computing the Core with SQL Queries (2009) (49)
On the complexity of the containment problem for conjunctive queries with built-in predicates (1998) (48)
Efficient Querying of Inconsistent Databases with Binary Integer Programming (2013) (47)
Semi-Automatic Schema Integration in Clio (2007) (43)
A Declarative Framework for Linking Entities (2016) (41)
Descriptive Complexity and Finite Models (1997) (40)
A Logical Approach to Constraint Satisfaction (2008) (37)
0-1 laws for infinitary logics (1990) (37)
EIRENE: Interactive Design and Refinement of Schema Mappings via Data Examples (2011) (35)
Existential second-order logic over graphs: charting the tractability frontier (2000) (34)
Invited Articles Foreword (2015) (33)
Constraint Satisfaction, Databases, and Logic (2003) (32)
Phase transitions of PP-complete satisfiability problems (2001) (32)
Dichotomies in the Complexity of Preferred Repairs (2015) (32)
Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics (2013) (29)
How to define a linear order on finite models (1994) (27)
Can Datalog be approximated? (1994) (27)
0-1 Laws for Fragments of Existential Second-Order Logic: A Survey (2000) (26)
Probabilistic data exchange (2010) (26)
On the Complexity of Existential Pebble Games (2003) (23)
Implicit Definability and Infinitary Logic in Finite Model Theory (1995) (22)
In nitary Logi s and 0-1 Laws (1992) (21)
The complexity of mining maximal frequent subgraphs (2013) (21)
On the expressive power of variable-confined logics (1996) (21)
Active Learning of GAV Schema Mappings (2018) (20)
Structural characterizations of schema-mapping languages (2009) (20)
Approximation Algorithms for Schema-Mapping Discovery from Data Examples (2017) (20)
An Introduction to Ontology-Based Query Answering with Existential Rules (2019) (20)
A SAT-based System for Consistent Query Answering (2019) (19)
A Dichotomy in the Complexity of Propositional Circumscription (2001) (19)
Laconic schema mappings: computing core universal solutions by means of SQL queries (2009) (19)
On the Expressive Power of Logics on Finite Models (2007) (18)
Probabilistic data exchange (2011) (18)
0-1 LAWS FOR FRAGMENTS OF SECOND-ORDER LOGIC: AN OVERVIEW (1990) (18)
On Asymptotic Probability of Inductive Queries and Their Decision Problem (1985) (18)
Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (2002) (17)
The Complexity of Mining Maximal Frequent Subgraphs (2014) (17)
Efficient Implementation of Large-Scale Multi-Structural Databases (2005) (16)
Nested dependencies: structure and reasoning (2014) (16)
Decision Problems in Information Theory (2020) (15)
Local transformations and conjunctive-query equivalence (2012) (15)
Bag Query Containment and Information Theory (2019) (15)
Foundations of information integration under bag semantics (2017) (14)
Random graphs and the parity quantifier (2009) (14)
Database Constraints and Homomorphism Dualities (2010) (13)
Data exchange with arithmetic operations (2013) (13)
The Complexity of Counting Problems in Equational Matching (1994) (13)
Limits of Schema Mappings (2017) (13)
Reflections on Schema Mappings, Data Exchange, and Metadata Management (2018) (12)
Database Theory — ICDT '97 (1997) (12)
Exchange-Repairs (2014) (12)
Closures and dichotomies for quantified constraints (2006) (11)
Preferred representations of Boolean relations (2005) (11)
Learning schema mappings (2013) (11)
Integer programming as a framework for optimization and approximability (1996) (10)
First-order logic vs. fixed-point logic in finite set theory (1999) (10)
Unification Algorithms Cannot Be Combined in Polynomial Time (1996) (10)
Computational Social Choice Meets Databases (2018) (9)
Infinitary Logic in Finite Model Theory (1997) (9)
On the Expressive Power of Homomorphism Counts (2021) (9)
Schema mappings and data examples (2011) (9)
Infinitary Logic for Computer Science (1992) (9)
Exchange, integration, and consistency of data: report on the ARISE/NISR workshop (2005) (9)
Paper and proposal reviews (2008) (8)
On the Data Complexity of Consistent Query Answering (2014) (8)
Database theory -- ICDT '97 : 6th International Conference, Delphi, Greece, January 8-10, 1997 : proceedings (1997) (8)
Expressive Power of Entity-Linking Frameworks (2019) (8)
On the Complexity of Counting the Hilbert Basis of a Linear Diophnatine System (1999) (8)
The Query Containment Problem: Set Semantics vs. Bag Semantics (2013) (7)
Logic and Learning (Dagstuhl Seminar 19361) (2019) (7)
Algorithmic Techniques for Necessary and Possible Winners (2020) (7)
Characterizing schema mappings via data examples (2010) (7)
On the Complexity of Model Checking and Inference in Minimal Models (2001) (7)
Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract) (1995) (6)
Languages for Polynomial-Time Queries - An Ongoing Quest (1995) (6)
Reasoning Web. Reasoning on the Web in the Big Data Era (2014) (5)
Consistent Answers of Aggregation Queries using SAT Solvers (2021) (5)
Generalized Satisfiability Problems via Operator Assignments (2017) (5)
Computational Complexity of Simultaneous Elementary Matching Problems (1999) (5)
Schema mappings and data examples (2013) (5)
Practical Query Answering in Data Exchange Under Inconsistency-Tolerant Semantics (2016) (5)
Fixed-point logics, descriptive complexity, and random satisfiability (2002) (5)
Proceedings of the 6th International Conference on Database Theory (1997) (5)
Temporal Enrichment and Querying of Ontology-Compliant Data (2020) (5)
Structure and Complexity of Bag Consistency (2020) (5)
On the boundedness problem for two-variable first-order logic (1998) (5)
On the tractability and intractability of consistent conjunctive query answering (2011) (5)
Query Evaluation in Election Databases (2019) (4)
EIRENE (2011) (4)
Polynomial-time optimization, parallel approximation, and fixpoint logic (1993) (4)
On the Complexity of Unification and Disunification in Commutative Idempotent Semigroups (1997) (4)
Peer data exchange (2005) (4)
Classifying the Complexity of the Possible Winner Problem on Partial Chains (2021) (4)
Recursion in a quantifier vs. elementary induction (1979) (4)
Aggregation of Votes with Multiple Positions on Each Issue (2015) (3)
Reflections on Finite Model Theory (2007) (3)
Complexity in databases, games, and logics (2006) (3)
CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving (2021) (3)
Comparing phase transitions and peak cost in PP-complete satisfiability problems (2002) (3)
Ontology-Enriched Query Answering on Relational Databases (2021) (3)
Logics for Dependence and Independence (Dagstuhl Seminar 19031) (2019) (3)
Consistency, Acyclicity, and Positive Semirings (2020) (2)
A Tutorial on Finite Model Theory (Abstract) (1993) (2)
Panel: logic in the computer science curriculum (1998) (2)
Dependence Logic vs. Constraint Satisfaction (2016) (2)
University of Illinois at Chicago, Chicago, IL, June 1–4, 2003 (2004) (2)
Consistent Answers of Conjunctive Queries on Graphs (2015) (2)
On the Computational Complexity of Non-dictatorial Aggregation (2017) (2)
Combinatorial games in database theory (1995) (2)
On the Language of Nested Tuple Generating Dependencies (2020) (2)
Random graphs and the parity quantifier (2009) (2)
Data Exchange, Integration, and Streams (2013) (2)
Constraint Satisfaction, Complexity, and Logic (2004) (2)
Exchange-Repairs (2016) (2)
Descriptive complexity and finite models : proceedings of a DIMACS workshop, January 14-17, 1996, Princeton University (1997) (2)
The Complexity of Possible Winners on Partial Chains (2020) (2)
On the Complexity of Counting the HilbertBasis of a Linear Diophantine (1999) (2)
Schema Mappings: A Case of Logical Dynamics in Database Theory (2014) (2)
0-1 Laws for Infinitary Logics (Preliminary Report) (1990) (2)
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability (2009) (1)
Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361) (2017) (1)
Bag Query Containment and Information Theory (2021) (1)
University of California Research Seminar Network: A Prospectus (2010) (1)
Consistent Answers of Aggregation Queries via SAT (2022) (1)
On recursion in E and semi-Spector classes (2016) (1)
On recursion in $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{E}$$and semi-spector classes (1978) (1)
Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk) (2011) (1)
Phase Transitions of Bounded Satisfiability Problems (2003) (1)
Recursion and Nonmonotone Induction in a Quantifier (1980) (1)
Model-theoretic Characterizations of Rule-based Ontologies (2021) (1)
Complexity of Constraints, 06401 (2006) (1)
Universal Solutions in Temporal Data Exchange (2020) (1)
The ACM PODS Alberto O. Mendelzon test-of-time-award 2009 (2009) (0)
Active Learning of GAV Mappings (2018) (0)
A Finer Analysis of Multi-Structural Games and Beyond (2023) (0)
Phase transitions of boolean satisfiability variants (2004) (0)
ON VARIANTS OF DEPENDENCE LOGIC (2015) (0)
Schema Mappings: Structural Properties and Limits (Invited Talk) (2017) (0)
Session details: Invited talk (2008) (0)
A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases (2023) (0)
Editor’s Note: Special Issue on Database Theory (2015) (0)
Bag ery Containment and Information Theory (2019) (0)
In Search of a Phase Transition in the AC-Matching Problem (2001) (0)
Proceedings 37th International Conference on Logic Programming (Technical Communications) (2021) (0)
Theory and Practice of Relational-to-RDF Temporal Data Exchange and Query Answering (2023) (0)
LICS 2003 special issue (2005) (0)
Session details: Tutorial Session (2012) (0)
Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (1995) (0)
Áñôðð Blockin Blockinø ¬òòòòððøý Òò Áò¬òòøøöý Äóóó Ò Òòøø Åóð Ìììóöý´´üøøòòòò (2007) (0)
DFU, Volume 5, Data Exchange, Integration, and Streams, Complete Volume (2013) (0)
The quest for a logic for polynomial-time computation (2011) (0)
Dedicated to the memory of Harald Ganzinger (2004) (0)
1995–1996 annual meeting of the association for symbolic logic (1996) (0)
Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
When do homomorphism counts help in query algorithms? (2023) (0)
Report on DEIS'10: advanced school on data exchange, information, and streams (A GI-Dagstuhl Seminar) (2011) (0)
Complexity of Constraints Dagstuhl Seminar (2006) (0)
Pseudo-Finite Model Theory (2001) (0)
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability (2009) (0)
Algorithmic Aspects of Information Theory (2023) (0)
Computational Social Choice and Incomplete Information (2021) (0)
Limits of Schema Mappings (2017) (0)
Knowledge Refinement via Rule Selection (2019) (0)
Çò Øøø Óñôððüüøý Óó Åóð Òò Òò Áòòòööò Ò Ååòòññð Åóð× (2007) (0)
The ACM PODS Alberto O. Mendelzon test-of-time-award 2010 (2010) (0)
SIGMOD Officers , Committees , and Awardees Chair Vice-Chair Secretary / (2005) (0)
Universal solutions for temporal data exchange (2021) (0)
Schema Mappings and Data Examples: An Interplay between Syntax and Semantics: Invited Presentation at the Fifth International Symposium on Games, Automata, Logics and Formal Verification (2014) (0)
Frontmatter, Table of Contents, Preface (2013) (0)
Áò Ëëëö Óó Èèè×× Ìööò××øøóò Ò Øøø ¹ååø Blockinòò Èöóóððñ Èèóóóóò º Ãóðððøø× Ììóññ× Êêaeðð (2007) (0)
The Semantics of Aggregate Queries in Data Exchange Revisited (2013) (0)
0-1 Laws and Decision Probleiiis for Fragments Second-Order Logic (1988) (0)
Foreword: Selected Papers from ICDT 1997 (2000) (0)
06401 Abstracts Collection - Complexity of Constraints (2006) (0)
SIGMOD: G: CAvSAT: A System forQuery Answering over Inconsistent Databases (2020) (0)
06401 Executive Summary - Complexity of Constraints (2006) (0)
Structure and Complexity of Bag Consistency (2022) (0)
Complexity of Constraints, 01.10. - 06.10.2006 (2006) (0)
Model theoretic characterizations in generalized recursion theory (1981) (0)
The Constraint Satisfaction Problem : Complexity and Approximability 3 CSP duality and trees of bounded pathwidth (2010) (0)
Association for Symbolic Logic (1996) (0)
Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
2020 NORTH AMERICAN ANNUAL MEETING OF THE ASSOCIATION FOR SYMBOLIC LOGIC University of California, Irvine Irvine, California, USA March 25–28, 2020 (2020) (0)
Report from Dagstuhl Seminar 17361 Finite and Algorithmic Model Theory (2018) (0)
The ACM PODS Alberto O. Mendelzon test-of-time award 2012 (2012) (0)

This paper list is powered by the following services:

Other Resources About Phokion G. Kolaitis

What Schools Are Affiliated With Phokion G. Kolaitis?

Phokion G. Kolaitis is affiliated with the following schools:

Phokion G. Kolaitis's Academic­Influence.com Rankings