Search Results

Documents authored by Ochremiak, Joanna

Document
DOI: 10.4230/DagRep.12.1.101
Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051)

Authors: Albert Atserias, Christoph Berkholz, Kousha Etessami, and Joanna Ochremiak

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

Abstract
Finite and algorithmic model theory (FAMT) studies the expressive power of logical languages on finite structures or, more generally, structures that can be finitely presented. These are the structures that serve as input to computation, and for this reason the study of FAMT is intimately connected with computer science. Over the last four decades, the subject has developed through a close interaction between theoretical computer science and related areas of mathematics, including logic and combinatorics. This report documents the program and the outcomes of Dagstuhl Seminar 22051 "Finite and Algorithmic Model Theory".
Cite as

Albert Atserias, Christoph Berkholz, Kousha Etessami, and Joanna Ochremiak. Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). In Dagstuhl Reports, Volume 12, Issue 1, pp. 101-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{atserias_et_al:DagRep.12.1.101,
  author =	{Atserias, Albert and Berkholz, Christoph and Etessami, Kousha and Ochremiak, Joanna},
  title =	{{Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051)}},
  pages =	{101--118},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Atserias, Albert and Berkholz, Christoph and Etessami, Kousha and Ochremiak, Joanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.1.101},
  URN =		{urn:nbn:de:0030-drops-169232},
  doi =		{10.4230/DagRep.12.1.101},
  annote =	{Keywords: automata and game theory, database theory, descriptive complexity, finite model theory, homomorphism counts, Query enumeration}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.110
Proof Complexity Meets Algebra

Authors: Albert Atserias and Joanna Ochremiak

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional and semi-algebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence and addition of constants to a core preserve the proof complexity of the CSP. As a result, for those proof systems, the classes of constraint languages for which small unsatisfiability certificates exist can be characterised algebraically. We illustrate our results by a gap theorem saying that a constraint language either has resolution refutations of bounded width, or does not have bounded-depth Frege refutations of subexponential size. The former holds exactly for the widely studied class of constraint languages of bounded width. This class is also known to coincide with the class of languages with Sums-of-Squares refutations of sublinear degree, a fact for which we provide an alternative proof. We hence ask for the existence of a natural proof system with good behaviour with respect to reductions and simultaneously small size refutations beyond bounded width. We give an example of such a proof system by showing that bounded-degree Lovasz-Schrijver satisfies both requirements.
Cite as

Albert Atserias and Joanna Ochremiak. Proof Complexity Meets Algebra. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 110:1-110:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.ICALP.2017.110,
  author =	{Atserias, Albert and Ochremiak, Joanna},
  title =	{{Proof Complexity Meets Algebra}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{110:1--110:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.110},
  URN =		{urn:nbn:de:0030-drops-74956},
  doi =		{10.4230/LIPIcs.ICALP.2017.110},
  annote =	{Keywords: Constraint Satisfaction Problem, Proof Complexity, Reductions, Gap Theorems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.14
Homomorphism Problems for First-Order Definable Structures

Authors: Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon Torunczyk

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We investigate several variants of the homomorphism problem: given two relational structures, is there a homomorphism from one to the other? The input structures are possibly infinite, but definable by first-order interpretations in a fixed structure. Their signatures can be either finite or infinite but definable. The homomorphisms can be either arbitrary, or definable with parameters, or definable without parameters. For each of these variants, we determine its decidability status.
Cite as

Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon Torunczyk. Homomorphism Problems for First-Order Definable Structures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{klin_et_al:LIPIcs.FSTTCS.2016.14,
  author =	{Klin, Bartek and Lasota, Slawomir and Ochremiak, Joanna and Torunczyk, Szymon},
  title =	{{Homomorphism Problems for First-Order Definable Structures}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.14},
  URN =		{urn:nbn:de:0030-drops-68498},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.14},
  annote =	{Keywords: Sets with atoms, first-order interpretations, homomorphism problem}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact