Phokion G. Kolaitis

Affiliations:
  • University of California, Santa Cruz, USA


According to our database1, Phokion G. Kolaitis authored at least 162 papers between 1979 and 2022.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2005, "For contributions to logic in computer science.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Structure and Complexity of Bag Consistency.
SIGMOD Rec., 2022

Consistent Answers of Aggregation Queries via SAT.
Proceedings of the 38th IEEE International Conference on Data Engineering, 2022

2021
Bag Query Containment and Information Theory.
ACM Trans. Database Syst., 2021

Algorithmic Techniques for Necessary and Possible Winners.
Trans. Data Sci., 2021

On the Computational Complexity of Non-Dictatorial Aggregation.
J. Artif. Intell. Res., 2021

Universal solutions for temporal data exchange.
Inf. Comput., 2021

Consistent Answers of Aggregation Queries using SAT Solvers.
CoRR, 2021

CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving.
Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

Computational Social Choice and Incomplete Information.
Proceedings of the 29th Italian Symposium on Advanced Database Systems, 2021

Model-theoretic Characterizations of Rule-based Ontologies.
Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

On the Expressive Power of Homomorphism Counts.
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Classifying the Complexity of the Possible Winner Problem on Partial Chains.
Proceedings of the AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, 2021

Ontology-Enriched Query Answering on Relational Databases.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
On the Language of Nested Tuple Generating Dependencies.
ACM Trans. Database Syst., 2020

Consistency, Acyclicity, and Positive Semirings.
CoRR, 2020

The Complexity of Possible Winners on Partial Chains.
CoRR, 2020

Decision Problems in Information Theory.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Temporal Enrichment and Querying of Ontology-Compliant Data.
Proceedings of the New Trends in Databases and Information Systems, 2020

2019
Aggregation of Votes with Multiple Positions on Each Issue.
ACM Trans. Economics and Comput., 2019

Expressive power of entity-linking frameworks.
J. Comput. Syst. Sci., 2019

Generalized satisfiability problems via operator assignments.
J. Comput. Syst. Sci., 2019

Logics for Dependence and Independence (Dagstuhl Seminar 19031).
Dagstuhl Reports, 2019

Logic and Learning (Dagstuhl Seminar 19361).
Dagstuhl Reports, 2019

A SAT-Based System for Consistent Query Answering.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

Query Evaluation in Election Databases.
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Knowledge Refinement via Rule Selection.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018
Limits of Schema Mappings.
Theory Comput. Syst., 2018

Reflections on Schema Mappings, Data Exchange, and Metadata Management.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Active Learning of GAV Schema Mappings.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Computational Social Choice Meets Databases.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

2017
Approximation Algorithms for Schema-Mapping Discovery from Data Examples.
ACM Trans. Database Syst., 2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).
Dagstuhl Reports, 2017

Foundations of information integration under bag semantics.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Schema Mappings: Structural Properties and Limits (Invited Talk).
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
A Declarative Framework for Linking Entities.
ACM Trans. Database Syst., 2016

Exchange-Repairs - Managing Inconsistency in Data Exchange.
J. Data Semant., 2016

Practical Query Answering in Data Exchange Under Inconsistency-Tolerant Semantics.
Proceedings of the 19th International Conference on Extending Database Technology, 2016

Dependence Logic vs. Constraint Satisfaction.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015
On the Data Complexity of Consistent Query Answering.
Theory Comput. Syst., 2015

Invited Articles Foreword.
J. ACM, 2015

Aggregation of Votes with Multiple Positions on Each Issue.
CoRR, 2015

Consistent Answers of Conjunctive Queries on Graphs.
CoRR, 2015

Dichotomies in the Complexity of Preferred Repairs.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014
The Complexity of Mining Maximal Frequent Subgraphs.
ACM Trans. Database Syst., 2014

Nested dependencies: structure and reasoning.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Schema Mappings: A Case of Logical Dynamics in Database Theory.
Proceedings of the Johan van Benthem on Logic and Information Dynamics, 2014

2013
Learning schema mappings.
ACM Trans. Database Syst., 2013

Efficient Querying of Inconsistent Databases with Binary Integer Programming.
Proc. VLDB Endow., 2013

Random graphs and the parity quantifier.
J. ACM, 2013

The Semantics of Aggregate Queries in Data Exchange Revisited.
Proceedings of the Scalable Uncertainty Management - 7th International Conference, 2013

Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics.
Proceedings of the IJCAI 2013, 2013

Schema mappings and data examples.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Data exchange with arithmetic operations.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

The Query Containment Problem: Set Semantics vs. Bag Semantics.
Proceedings of the 7th Alberto Mendelzon International Workshop on Foundations of Data Management, 2013

2012
A dichotomy in the complexity of consistent query answering for queries with two atoms.
Inf. Process. Lett., 2012

The ACM PODS Alberto O. Mendelzon test-of-time award 2012.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Local transformations and conjunctive-query equivalence.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

2011
Reverse data exchange: Coping with nulls.
ACM Trans. Database Syst., 2011

Characterizing schema mappings via data examples.
ACM Trans. Database Syst., 2011

Report on DEIS'10: advanced school on data exchange, information, and streams (A GI-Dagstuhl Seminar).
SIGMOD Rec., 2011

EIRENE: Interactive Design and Refinement of Schema Mappings via Data Examples.
Proc. VLDB Endow., 2011

Probabilistic data exchange.
J. ACM, 2011

The quest for a logic for polynomial-time computation: technical perspective.
Commun. ACM, 2011

Designing and refining schema mappings via data examples.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

Schema mappings and data examples.
Proceedings of the 4th International Workshop on Logic in Databases, 2011

Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

On the tractability and intractability of consistent conjunctive query answering.
Proceedings of the 2011 Joint EDBT/ICDT Ph.D. Workshop, Uppsala, Sweden, March 25, 2011, 2011

Schema Mapping Evolution Through Composition and Inversion.
Proceedings of the Schema Matching and Mapping, 2011

2010
Structural characterizations of schema-mapping languages.
Commun. ACM, 2010

The ACM PODS Alberto O. Mendelzon test-of-time-award 2010.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Characterizing schema mappings via data examples.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Database Constraints and Homomorphism Dualities.
Proceedings of the Principles and Practice of Constraint Programming - CP 2010, 2010

2009
Laconic Schema Mappings: Computing the Core with SQL Queries.
Proc. VLDB Endow., 2009

Laconic schema mappings: computing core universal solutions by means of SQL queries
CoRR, 2009

The ACM PODS Alberto O. Mendelzon test-of-time-award 2009.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Repair checking in inconsistent databases: algorithms and complexity.
Proceedings of the Database Theory, 2009

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

2008
Quasi-inverses of schema mappings.
ACM Trans. Database Syst., 2008

Paper and proposal reviews: is the process flawed?
SIGMOD Rec., 2008

Structure identification of Boolean relations and plain bases for co-clones.
J. Comput. Syst. Sci., 2008

Interactive generation of integrated schemas.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Towards a theory of schema-mapping optimization.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Answering aggregate queries in data exchange.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

A Logical Approach to Constraint Satisfaction.
Proceedings of the Complexity of Constraints, 2008

2007
Finite Model Theory and Its Applications
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-68804-4, 2007

Phase transitions of PP-complete satisfiability problems.
Discret. Appl. Math., 2007

Semi-Automatic Schema Integration in Clio.
Proceedings of the 33rd International Conference on Very Large Data Bases, 2007

Reflections on Finite Model Theory.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

2006
Peer data exchange.
ACM Trans. Database Syst., 2006

On preservation under homomorphisms and unions of conjunctive queries.
J. ACM, 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
Electron. Colloquium Comput. Complex., 2006

Closures and dichotomies for quantified constraints.
Electron. Colloquium Comput. Complex., 2006

The complexity of data exchange.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

The containment problem for REAL conjunctive queries with inequalities.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

06401 Abstracts Collection - Complexity of Constraints.
Proceedings of the Complexity of Constraints, 01.10. - 06.10.2006, 2006

06401 Executive Summary - Complexity of Constraints.
Proceedings of the Complexity of Constraints, 01.10. - 06.10.2006, 2006

2005
Composing schema mappings: Second-order dependencies to the rescue.
ACM Trans. Database Syst., 2005

Data exchange: getting to the core.
ACM Trans. Database Syst., 2005

LICS 2003 special issue.
ACM Trans. Comput. Log., 2005

Data exchange: semantics and query answering.
Theor. Comput. Sci., 2005

Subtractive reductions and complete problems for counting complexity classes.
Theor. Comput. Sci., 2005

Exchange, integration, and consistency of data: report on the ARISE/NISR workshop.
SIGMOD Rec., 2005

Preferred representations of Boolean relations
Electron. Colloquium Comput. Complex., 2005

Efficient Implementation of Large-Scale Multi-Structural Databases.
Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30, 2005

Schema mappings, data exchange, and metadata management.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

2004
Foreword.
ACM Trans. Database Syst., 2004

A Dichotomy in the Complexity of Propositional Circumscription.
Theory Comput. Syst., 2004

Foreword.
J. ACM, 2004

Existential second-order logic over graphs: Charting the tractability frontier.
J. ACM, 2004

Constraint Satisfaction, Complexity, and Logic.
Proceedings of the Methods and Applications of Artificial Intelligence, 2004

Constraint Propagation as a Proof System.
Proceedings of the Principles and Practice of Constraint Programming, 2004

2003
Constraint Satisfaction, Databases, and Logic.
Proceedings of the IJCAI-03, 2003

Phase Transitions of Bounded Satisfiability Problems.
Proceedings of the IJCAI-03, 2003

On the Complexity of Existential Pebble Games.
Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002
Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.
Proceedings of the Principles and Practice of Constraint Programming, 2002

Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems.
Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28, 2002

2001
On the unusual effectiveness of logic in computer science.
Bull. Symb. Log., 2001

On the Complexity of Model Checking and Inference in Minimal Models.
Proceedings of the Logic Programming and Nonmonotonic Reasoning, 2001

In Search of a Phase Transition in the AC-Matching Problem.
Proceedings of the Principles and Practice of Constraint Programming, 2001

2000
Foreword: Selected Papers from ICDT 1997.
Theor. Comput. Sci., 2000

Conjunctive-Query Containment and Constraint Satisfaction.
J. Comput. Syst. Sci., 2000

Unification Algorithms Cannot Be Combined in Polynomial Time.
Inf. Comput., 2000

The Complexity of Minimal Satisfiability Problems
Electron. Colloquium Comput. Complex., 2000

0-1 Laws for Fragments of Existential Second-Order Logic: A Survey.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

A Game-Theoretic Approach to Constraint Satisfaction.
Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30, 2000

1999
Computational Complexity of Simultaneous Elementary Matching Problems.
J. Autom. Reason., 1999

On the Complexity of Counting the Hilbert Basis of a Linear Diophnatine System.
Proceedings of the Logic Programming and Automated Reasoning, 6th International Conference, 1999

First-Order Logic vs. Fixed-Point Logic in Finite Set Theory.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

1998
Integer Programming as a Framework for Optimization and Approximability.
J. Comput. Syst. Sci., 1998

Panel: logic in the computer science curriculum.
Proceedings of the 29th SIGCSE Technical Symposium on Computer Science Education, 1998

On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

On the Boundedness Problem for Two-Variable First-Order Logic.
Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1997
Can Datalog Be Approximated?
J. Comput. Syst. Sci., 1997

On the decision problem for two-variable first-order logic.
Bull. Symb. Log., 1997

How to Define a Linear Order on Finite Models.
Ann. Pure Appl. Log., 1997

On the Complexity of Unification and Disunification in Commutative Idempotent Semigroups.
Proceedings of the Principles and Practice of Constraint Programming - CP97, Third International Conference, Linz, Austria, October 29, 1997

1996
Almost everywhere equivalence of logics in finite model theory.
Bull. Symb. Log., 1996

On the Expressive Power of Variable-Confined Logics.
Proceedings of the Proceedings, 1996

1995
The Complexity of Counting Problems in Equational Matching.
J. Symb. Comput., 1995

On the Expressive Power of Datalog: Tools and a Case Study.
J. Comput. Syst. Sci., 1995

Approximation Properties of NP Minimization Classes.
J. Comput. Syst. Sci., 1995

Generalized Quantifiers and Pebble Games on Finite Structures.
Ann. Pure Appl. Log., 1995

Combinatorial Games In Database Theory.
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1995

Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Languages for Polynomial-Time Queries - An Ongoing Quest.
Proceedings of the Database Theory, 1995

Implicit Definability and Infinitary Logic in Finite Model Theory.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994
Logical Definability of NP Optimization Problems
Inf. Comput., December, 1994

1993
A Tutorial on Finite Model Theory (Abstract)
Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

Polynomial-time Optimization, Parallel Approximation, and Fixpoint Logic (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, 1993

1992
Infinitary Logics and 0-1 Laws
Inf. Comput., June, 1992

Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory
Proceedings of the Seventh Annual Symposium on Logic in Computer Science (LICS '92), 1992

Infinitary Logic for Computer Science.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
The Expressive Power of Stratified Programs
Inf. Comput., January, 1991

Why not Negation by Fixpoint?
J. Comput. Syst. Sci., 1991

1990
Some Computational Aspects of Circumscription
J. ACM, January, 1990

0-1 Laws and Decision Problems for Fragments of Second-Order Logic
Inf. Comput., 1990

0-1 Laws for Infinitary Logics (Preliminary Report)
Proceedings of the Fifth Annual Symposium on Logic in Computer Science (LICS '90), 1990

Implicit Definability on Finite Structures and Unambiguous Computations (Preliminary Report)
Proceedings of the Fifth Annual Symposium on Logic in Computer Science (LICS '90), 1990

1987
The Decision Problem for the Probabilities of Higher-Order Properties
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1985
On Asymptotic Probability of Inductive Queries and Their Decision Problem.
Proceedings of the Logics of Programs, 1985

1979
Recursion in a Quantifier vs. Elementary Induction.
J. Symb. Log., 1979


  Loading...