42 Search Results for "Kolaitis, Phokion"

Volume

Dagstuhl Follow-Ups, Volume 5

Data Exchange, Integration, and Streams

Editors: Phokion G. Kolaitis, Maurizio Lenzerini, and Nicole Schweikardt

Document
DOI: 10.4230/DagRep.12.7.180
Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301)

Authors: Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studený, Dan Suciu, and Tobias A. Boege

Published in: Dagstuhl Reports, Volume 12, Issue 7 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22301 "Algorithmic Aspects of Information Theory". Constraints on entropies constitute the "laws of information theory". These constraints go well beyond Shannon’s basic information inequalities, as they include not only information inequalities that cannot be derived from Shannon’s basic inequalities, but also conditional inequalities and disjunctive inequalities that are valid for all entropic functions. There is an extensive body of research on constraints on entropies and their applications to different areas of mathematics and computer science. So far, however, little progress has been made on the algorithmic aspects of information theory. In fact, even fundamental questions about the decidability of information inequalities and their variants have remained open to date. Recently, research in different applications has demonstrated a clear need for algorithmic solutions to questions in information theory. These applications include: finding tight upper bounds on the answer to a query on a relational database, the homomorphism domination problem and its uses in query optimization, the conditional independence implication problem, soft constraints in databases, group-theoretic inequalities, and lower bounds on the information ratio in secret sharing. Thus far, the information-theory community has had little interaction with the communities where these applications have been studied or with the computational complexity community. The main goal of this Dagstuhl Seminar was to bring together researchers from the aforementioned communities and to develop an agenda for studying algorithmic aspects of information theory, motivated from a rich set of diverse applications. By using the algorithmic lens to examine the common problems and by transferring techniques from one community to the other, we expected that bridges would be created and some tangible progress on open questions could be made.
Cite as

Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studený, Dan Suciu, and Tobias A. Boege. Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301). In Dagstuhl Reports, Volume 12, Issue 7, pp. 180-204, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{kolaitis_et_al:DagRep.12.7.180,
  author =	{Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.},
  title =	{{Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301)}},
  pages =	{180--204},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{7},
  editor =	{Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.7.180},
  URN =		{urn:nbn:de:0030-drops-176155},
  doi =		{10.4230/DagRep.12.7.180},
  annote =	{Keywords: Information theory, Information inequalities, Conditional independence structures, Database query evaluation and containment, Decision problems}
}
Document
DOI: 10.4230/DagRep.12.2.1
Logic and Random Discrete Structures (Dagstuhl Seminar 22061)

Authors: Erich Grädel, Phokion G. Kolaitis, Marc Noy, and Matthias Naaf

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22061 "Logic and Random Discrete Structures". The main topic of this seminar has been the analysis of large random discrete structures, such as trees, graphs, or permutations, from the perspective of mathematical logic. It has brought together both experts and junior researchers from a number of different areas where logic and random structures play a role, with the goal to establish new connections between such areas and to encourage interactions between foundational research and different application areas, including probabilistic databases.
Cite as

Erich Grädel, Phokion G. Kolaitis, Marc Noy, and Matthias Naaf. Logic and Random Discrete Structures (Dagstuhl Seminar 22061). In Dagstuhl Reports, Volume 12, Issue 2, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gradel_et_al:DagRep.12.2.1,
  author =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Noy, Marc and Naaf, Matthias},
  title =	{{Logic and Random Discrete Structures (Dagstuhl Seminar 22061)}},
  pages =	{1--16},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Noy, Marc and Naaf, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.1},
  URN =		{urn:nbn:de:0030-drops-169295},
  doi =		{10.4230/DagRep.12.2.1},
  annote =	{Keywords: combinatorics, complexity theory, logic, random structures, probabilistic databases}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2022.1
On an Information Theoretic Approach to Cardinality Estimation (Invited Talk)

Authors: Hung Q. Ngo

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
This article is a companion to an invited talk at ICDT'2022 with the same title. Cardinality estimation is among the most important problems in query optimization. It is well-documented that, when query plans go haywire, in most cases one can trace the root cause to the cardinality estimator being far off. In particular, traditional cardinality estimation based on selectivity estimation may sometimes under-estimate cardinalities by orders of magnitudes, because the independence or the uniformity assumptions do not typically hold. This talk outlines an approach to cardinality estimation that is "model-free" from a statistical stand-point. Being model-free means the approach tries to avoid making any distributional assumptions. Our approach is information-theoretic, and generalizes recent results on worst-case output size bounds of queries, allowing the estimator to take into account histogram information from the input relations. The estimator turns out to be the objective of a maximization problem subject to concave constraints, over an exponential number of variables. We then explain how the estimator can be computed in polynomial time for some fragment of these constraints. Overall, the talk introduces a new direction to address the classic problem of cardinality estimation that is designed to circumvent some of the pitfalls of selectivity-based estimation. We will also explain connections to other fundamental problems in information theory and database theory regarding information inequalities. The talk is based on (published and unpublished) joint works with Mahmoud Abo Khamis, Sungjin Im, Hossein Keshavarz, Phokion Kolaitis, Ben Moseley, XuanLong Nguyen, Kirk Pruhs, Dan Suciu, and Alireza Samadian Zakaria
Cite as

Hung Q. Ngo. On an Information Theoretic Approach to Cardinality Estimation (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 1:1-1:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ngo:LIPIcs.ICDT.2022.1,
  author =	{Ngo, Hung Q.},
  title =	{{On an Information Theoretic Approach to Cardinality Estimation}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.1},
  URN =		{urn:nbn:de:0030-drops-158750},
  doi =		{10.4230/LIPIcs.ICDT.2022.1},
  annote =	{Keywords: Cardinality Estimation, Information Theory, Polymatroid Bound, Worst-case Optimal Join}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2021.9
Conjunctive Queries: Unique Characterizations and Exact Learnability

Authors: Balder ten Cate and Victor Dalmau

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)

Abstract
We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.
Cite as

Balder ten Cate and Victor Dalmau. Conjunctive Queries: Unique Characterizations and Exact Learnability. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 9:1-9:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.ICDT.2021.9,
  author =	{ten Cate, Balder and Dalmau, Victor},
  title =	{{Conjunctive Queries: Unique Characterizations and Exact Learnability}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.9},
  URN =		{urn:nbn:de:0030-drops-137172},
  doi =		{10.4230/LIPIcs.ICDT.2021.9},
  annote =	{Keywords: Conjunctive Queries, Homomorphisms, Frontiers, Unique Characterizations, Exact Learnability, Schema Mappings, Description Logic}
}
Document
DOI: 10.4230/LIPIcs.TIME.2020.8
Universal Solutions in Temporal Data Exchange

Authors: Zehui Cheng and Phokion G. Kolaitis

Published in: LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)

Abstract
During the past fifteen years, data exchange has been explored in depth and in a variety of different settings. Even though temporal databases constitute a mature area of research studied over several decades, the investigation of temporal data exchange was initiated only very recently. We analyze the properties of universal solutions in temporal data exchange with emphasis on the relationship between universal solutions in the context of concrete time and universal solutions in the context of abstract time. We show that challenges arise even in the setting in which the data exchange specifications involve a single temporal variable. After this, we identify settings, including data exchange settings that involve multiple temporal variables, in which these challenges can be overcome.
Cite as

Zehui Cheng and Phokion G. Kolaitis. Universal Solutions in Temporal Data Exchange. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 8:1-8:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.TIME.2020.8,
  author =	{Cheng, Zehui and Kolaitis, Phokion G.},
  title =	{{Universal Solutions in Temporal Data Exchange}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.8},
  URN =		{urn:nbn:de:0030-drops-129763},
  doi =		{10.4230/LIPIcs.TIME.2020.8},
  annote =	{Keywords: temporal databases, database dependencies, data exchange, universal solutions, abstract time, concrete time, Allen’s relations}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.106
Decision Problems in Information Theory

Authors: Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Constraints on entropies are considered to be the laws of information theory. Even though the pursuit of their discovery has been a central theme of research in information theory, the algorithmic aspects of constraints on entropies remain largely unexplored. Here, we initiate an investigation of decision problems about constraints on entropies by placing several different such problems into levels of the arithmetical hierarchy. We establish the following results on checking the validity over all almost-entropic functions: first, validity of a Boolean information constraint arising from a monotone Boolean formula is co-recursively enumerable; second, validity of "tight" conditional information constraints is in Π⁰₃. Furthermore, under some restrictions, validity of conditional information constraints "with slack" is in Σ⁰₂, and validity of information inequality constraints involving max is Turing equivalent to validity of information inequality constraints (with no max involved). We also prove that the classical implication problem for conditional independence statements is co-recursively enumerable.
Cite as

Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu. Decision Problems in Information Theory. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 106:1-106:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abokhamis_et_al:LIPIcs.ICALP.2020.106,
  author =	{Abo Khamis, Mahmoud and Kolaitis, Phokion G. and Ngo, Hung Q. and Suciu, Dan},
  title =	{{Decision Problems in Information Theory}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{106:1--106:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.106},
  URN =		{urn:nbn:de:0030-drops-125137},
  doi =		{10.4230/LIPIcs.ICALP.2020.106},
  annote =	{Keywords: Information theory, decision problems, arithmetical hierarchy, entropic functions}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.13
Distribution Constraints: The Chase for Distributed Data

Authors: Gaetano Geck, Frank Neven, and Thomas Schwentick

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
This paper introduces a declarative framework to specify and reason about distributions of data over computing nodes in a distributed setting. More specifically, it proposes distribution constraints which are tuple and equality generating dependencies (tgds and egds) extended with node variables ranging over computing nodes. In particular, they can express co-partitioning constraints and constraints about range-based data distributions by using comparison atoms. The main technical contribution is the study of the implication problem of distribution constraints. While implication is undecidable in general, relevant fragments of so-called data-full constraints are exhibited for which the corresponding implication problems are complete for EXPTIME, PSPACE and NP. These results yield bounds on deciding parallel-correctness for conjunctive queries in the presence of distribution constraints.
Cite as

Gaetano Geck, Frank Neven, and Thomas Schwentick. Distribution Constraints: The Chase for Distributed Data. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 13:1-13:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{geck_et_al:LIPIcs.ICDT.2020.13,
  author =	{Geck, Gaetano and Neven, Frank and Schwentick, Thomas},
  title =	{{Distribution Constraints: The Chase for Distributed Data}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.13},
  URN =		{urn:nbn:de:0030-drops-119378},
  doi =		{10.4230/LIPIcs.ICDT.2020.13},
  annote =	{Keywords: tuple-generating dependencies, chase, conjunctive queries, distributed evaluation}
}
Document
DOI: 10.4230/DagRep.9.9.1
Logic and Learning (Dagstuhl Seminar 19361)

Authors: Michael Benedikt, Kristian Kersting, Phokion G. Kolaitis, and Daniel Neider

Published in: Dagstuhl Reports, Volume 9, Issue 9 (2020)

Abstract
The goal of building truly intelligent systems has forever been a central problem in computer science. While logic-based approaches of yore have had their successes and failures, the era of machine learning, specifically deep learning is also coming upon significant challenges. There is a growing consensus that the inductive reasoning and complex, high-dimensional pattern recognition capabilities of deep learning models need to be combined with symbolic (even programmatic), deductive capabilities traditionally developed in the logic and automated reasoning communities in order to achieve the next step towards building intelligent systems, including making progress at the frontier of hard problems such as explainable AI. However, these communities tend to be quite separate and interact only minimally, often at odds with each other upon the subject of the ``correct approach'' to AI. This report documents the efforts of Dagstuhl Seminar 19361 on ``Logic and Learning'' to bring these communities together in order to: (i) bridge the research efforts between them and foster an exchange of ideas in order to create unified formalisms and approaches that bear the advantages of both research methodologies; (ii) review and analyse the progress made across both communities; (iii) understand the subtleties and difficulties involved in solving hard problems using both perspectives; (iv) make attempts towards a consensus on what the hard problems are and what the elements of good solutions to these problems would be. The three focal points of the seminar were the strands of ``Logic for Machine Learning'', ``Machine Learning for Logic'', and ``Logic vs. Machine Learning''. The seminar format consisted of long and short talks, as well as breakout sessions. We summarise the motivations and proceedings of the seminar, and report on the abstracts of the talks and the results of the breakout sessions.
Cite as

Michael Benedikt, Kristian Kersting, Phokion G. Kolaitis, and Daniel Neider. Logic and Learning (Dagstuhl Seminar 19361). In Dagstuhl Reports, Volume 9, Issue 9, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{benedikt_et_al:DagRep.9.9.1,
  author =	{Benedikt, Michael and Kersting, Kristian and Kolaitis, Phokion G. and Neider, Daniel},
  title =	{{Logic and Learning (Dagstuhl Seminar 19361)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{9},
  number =	{9},
  editor =	{Benedikt, Michael and Kersting, Kristian and Kolaitis, Phokion G. and Neider, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.9.1},
  URN =		{urn:nbn:de:0030-drops-118425},
  doi =		{10.4230/DagRep.9.9.1},
  annote =	{Keywords: Artificial Intelligence, Automated reasoning, Databases, Deep Learning, Inductive Logic Programming, Logic, Logic and Learning, Logic for Machine Learning, Logic vs. Machine Learning, Machine Learning, Machine Learning for Logic, Neurosymbolic methods}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.50
Algorithmically Efficient Syntactic Characterization of Possibility Domains

Authors: Josep Díaz, Lefteris Kirousis, Sofia Kokonezi, and John Livieratos

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We call domain any arbitrary subset of a Cartesian power of the set {0,1} when we think of it as reflecting abstract rationality restrictions on vectors of two-valued judgments on a number of issues. In Computational Social Choice Theory, and in particular in the theory of judgment aggregation, a domain is called a possibility domain if it admits a non-dictatorial aggregator, i.e. if for some k there exists a unanimous (idempotent) function F:D^k - > D which is not a projection function. We prove that a domain is a possibility domain if and only if there is a propositional formula of a certain syntactic form, sometimes called an integrity constraint, whose set of satisfying truth assignments, or models, comprise the domain. We call possibility integrity constraints the formulas of the specific syntactic type we define. Given a possibility domain D, we show how to construct a possibility integrity constraint for D efficiently, i.e, in polynomial time in the size of the domain. We also show how to distinguish formulas that are possibility integrity constraints in linear time in the size of the input formula. Finally, we prove the analogous results for local possibility domains, i.e. domains that admit an aggregator which is not a projection function, even when restricted to any given issue. Our result falls in the realm of classical results that give syntactic characterizations of logical relations that have certain closure properties, like e.g. the result that logical relations component-wise closed under logical AND are precisely the models of Horn formulas. However, our techniques draw from results in judgment aggregation theory as well from results about propositional formulas and logical relations.
Cite as

Josep Díaz, Lefteris Kirousis, Sofia Kokonezi, and John Livieratos. Algorithmically Efficient Syntactic Characterization of Possibility Domains. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 50:1-50:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.ICALP.2019.50,
  author =	{D{\'\i}az, Josep and Kirousis, Lefteris and Kokonezi, Sofia and Livieratos, John},
  title =	{{Algorithmically Efficient Syntactic Characterization of Possibility Domains}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.50},
  URN =		{urn:nbn:de:0030-drops-106269},
  doi =		{10.4230/LIPIcs.ICALP.2019.50},
  annote =	{Keywords: collective decision making, computational social choice, judgment aggregation, logical relations, algorithm complexity}
}
Document
DOI: 10.4230/DagRep.9.1.28
Logics for Dependence and Independence (Dagstuhl Seminar 19031)

Authors: Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 19031 "Logics for Dependence and Independence". This seminar served as a follow-up seminar to the highly successful seminars "Dependence Logic: Theory and Applications" (13071) and "Logics for Dependence and Independence" (15261). A key objective of the seminar was to bring together researchers working in dependence logic and in the application areas so that they can communicate state-of-the-art advances and embark on a systematic interaction. The goal was especially to reach those researchers who have recently started working in this thriving area as well as researchers working on several aspects of database theory, separation logic, and logics of uncertainy.
Cite as

Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, and Heribert Vollmer. Logics for Dependence and Independence (Dagstuhl Seminar 19031). In Dagstuhl Reports, Volume 9, Issue 1, pp. 28-46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{gradel_et_al:DagRep.9.1.28,
  author =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Logics for Dependence and Independence (Dagstuhl Seminar 19031)}},
  pages =	{28--46},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Kontinen, Juha and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.28},
  URN =		{urn:nbn:de:0030-drops-105682},
  doi =		{10.4230/DagRep.9.1.28},
  annote =	{Keywords: dependence logic, mathematical logic, computational complexity, finite model theory, game theory}
}
Document
DOI: 10.4230/DagRep.7.9.1
Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361)

Authors: Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick

Published in: Dagstuhl Reports, Volume 7, Issue 9 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17361 "Finite and Algorithmic Model Theory".
Cite as

Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick. Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361). In Dagstuhl Reports, Volume 7, Issue 9, pp. 1-25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{dawar_et_al:DagRep.7.9.1,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Kolaitis, Phokion G. and Schwentick, Thomas},
  title =	{{Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361)}},
  pages =	{1--25},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{9},
  editor =	{Dawar, Anuj and Gr\"{a}del, Erich and Kolaitis, Phokion G. and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.9.1},
  URN =		{urn:nbn:de:0030-drops-85863},
  doi =		{10.4230/DagRep.7.9.1},
  annote =	{Keywords: algorithms, database theory, descriptive complexity, finite model theory, independence logic, knowledge representation, model checking}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2017.2
Schema Mappings: Structural Properties and Limits (Invited Talk)

Authors: Phokion G. Kolaitis

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
A schema mapping is a high-level specification of the relationship between two database schemas. For the past fifteen years, schema mappings have played an essential role in the modeling and analysis of important data inter-operability tasks, such as data exchange and data integration. Syntactically, schema mappings are expressed in some schema-mapping language, which, typically, is a fragment of first-order logic or second-order logic. In the first part of the talk, we will introduce the main schema-mapping languages, will discuss the fundamental structural properties of these languages, and will then use these structural properties to obtain characterizations of various schema-mapping languages in the spirit of abstract model theory. In the second part of the talk, we will examine schema mappings from a dynamic viewpoint by considering sequences of schema mappings and studying the convergence properties of such sequences. To this effect, we will introduce a metric space that is based on a natural notion of distance between sets of database instances and will investigate pointwise limits and uniform limits of sequences of schema mappings. Among other findings, it will turn out that the completion of this metric space can be described in terms of graph limits arising from converging sequences of homomorphism densities.
Cite as

Phokion G. Kolaitis. Schema Mappings: Structural Properties and Limits (Invited Talk). In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kolaitis:LIPIcs.CSL.2017.2,
  author =	{Kolaitis, Phokion G.},
  title =	{{Schema Mappings: Structural Properties and Limits}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.2},
  URN =		{urn:nbn:de:0030-drops-76707},
  doi =		{10.4230/LIPIcs.CSL.2017.2},
  annote =	{Keywords: logic and databases, schema mappings, data exchange, metric spaces}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.10
Expressive Power of Entity-Linking Frameworks

Authors: Douglas Burdick, Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We develop a unifying approach to declarative entity linking by introducing the notion of an entity linking framework and an accompanying notion of the certain links in such a framework. In an entity linking framework, logic-based constraints are used to express properties of the desired link relations in terms of source relations and, possibly, in terms of other link relations. The definition of the certain links in such a framework makes use of weighted repairs and consistent answers in inconsistent databases. We demonstrate the modeling capabilities of this approach by showing that numerous concrete entity linking scenarios can be cast as such entity linking frameworks for suitable choices of constraints and weights. By using the certain links as a measure of expressive power, we investigate the relative expressive power of several entity linking frameworks and obtain sharp comparisons. In particular, we show that we gain expressive power if we allow constraints that capture non-recursive collective entity resolution, where link relations may depend on other link relations (and not just on source relations). Moreover, we show that an increase in expressive power also takes place when we allow constraints that incorporate preferences as an additional mechanism for expressing "goodness" of links.
Cite as

Douglas Burdick, Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. Expressive Power of Entity-Linking Frameworks. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burdick_et_al:LIPIcs.ICDT.2017.10,
  author =	{Burdick, Douglas and Fagin, Ronald and Kolaitis, Phokion G. and Popa, Lucian and Tan, Wang-Chiew},
  title =	{{Expressive Power of Entity-Linking Frameworks}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.10},
  URN =		{urn:nbn:de:0030-drops-70554},
  doi =		{10.4230/LIPIcs.ICDT.2017.10},
  annote =	{Keywords: entity linking, entity resolution, constraints, repairs, certain links}
}
Document
DOI: 10.4230/LIPIcs.CSL.2016.14
Dependence Logic vs. Constraint Satisfaction

Authors: Lauri Hella and Phokion G. Kolaitis

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
During the past decade, dependence logic has emerged as a formalism suitable for expressing and analyzing notions of dependence and independence that arise in different scientific areas. The sentences of dependence logic have the same expressive power as those of existential second-order logic, hence dependence logic captures NP on the class of all finite structures. In this paper, we identify a natural fragment of universal dependence logic and show that, in a precise sense, it captures constraint satisfaction. This tight connection between dependence logic and constraint satisfaction contributes to the descriptive complexity of constraint satisfaction and elucidates the expressive power of universal dependence logic.
Cite as

Lauri Hella and Phokion G. Kolaitis. Dependence Logic vs. Constraint Satisfaction. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 14:1-14:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hella_et_al:LIPIcs.CSL.2016.14,
  author =	{Hella, Lauri and Kolaitis, Phokion G.},
  title =	{{Dependence Logic vs. Constraint Satisfaction}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.14},
  URN =		{urn:nbn:de:0030-drops-65548},
  doi =		{10.4230/LIPIcs.CSL.2016.14},
  annote =	{Keywords: Dependence logic, constraint satisfaction, computational complexity, expressive power}
}
  • Refine by Author
  • 17 Kolaitis, Phokion G.
  • 3 Grohe, Martin
  • 3 Grädel, Erich
  • 3 Vollmer, Heribert
  • 2 Bulatov, Andrei A.
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Information theory
  • 2 Theory of computation → Logic
  • 1 Information systems → Data management systems
  • 1 Information systems → Database design and models
  • 1 Information systems → Join algorithms
  • Show More...

  • Refine by Keyword
  • 6 data exchange
  • 5 computational complexity
  • 3 Data integration
  • 3 complexity
  • 3 finite model theory
  • Show More...

  • Refine by Type
  • 41 document
  • 1 volume

  • Refine by Publication Year
  • 13 2013
  • 7 2006
  • 5 2010
  • 4 2020
  • 2 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact