2 Search Results for "Vinall-Smeeth, Harry"

Document
DOI: 10.4230/LIPIcs.MFCS.2024.34
On the Number of Quantifiers Needed to Define Boolean Functions

Authors: Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, and Rik Sengupta

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binary strings with an ordering relation, using a technique we call parallel play, which significantly reduces the number of quantifiers needed in many cases. Ordered structures such as strings have historically been notoriously difficult to analyze in the context of these and similar games. Nevertheless, in this paper, we provide essentially tight bounds on the number of quantifiers needed to characterize different-sized subsets of strings. The results immediately give bounds on the number of quantifiers necessary to define several different classes of Boolean functions. One of our results is analogous to Lupanov’s upper bounds on circuit size and formula size in propositional logic: we show that every Boolean function on n-bit inputs can be defined by a FO sentence having (1+ε)n/log(n) + O(1) quantifiers, and that this is essentially tight. We reduce this number to (1 + ε)log(n) + O(1) when the Boolean function in question is sparse.
Cite as

Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, and Rik Sengupta. On the Number of Quantifiers Needed to Define Boolean Functions. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.MFCS.2024.34,
  author =	{Carmosino, Marco and Fagin, Ronald and Immerman, Neil and Kolaitis, Phokion G. and Lenchner, Jonathan and Sengupta, Rik},
  title =	{{On the Number of Quantifiers Needed to Define Boolean Functions}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.34},
  URN =		{urn:nbn:de:0030-drops-205907},
  doi =		{10.4230/LIPIcs.MFCS.2024.34},
  annote =	{Keywords: logic, combinatorial games, Boolean functions, quantifier number}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.113
A Dichotomy for Succinct Representations of Homomorphisms

Authors: Christoph Berkholz and Harry Vinall-Smeeth

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The task of computing homomorphisms between two finite relational structures A and B is a well-studied question with numerous applications. Since the set Hom(A, B) of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient enumeration and counting, could be extremely useful. One simple yet powerful way of doing so is to decompose Hom(A, B) using union and Cartesian product. Such data structures, called d-representations, have been introduced by Olteanu and Závodný [Olteanu and Závodný, 2015] in the context of database theory. Their results also imply that if the treewidth of the left-hand side structure A is bounded, then a d-representation of polynomial size can be found in polynomial time. We show that for structures of bounded arity this is optimal: if the treewidth is unbounded then there are instances where the size of any d-representation is superpolynomial. Along the way we develop tools for proving lower bounds on the size of d-representations, in particular we define a notion of reduction suitable for this context and prove an almost tight lower bound on the size of d-representations of all k-cliques in a graph.
Cite as

Christoph Berkholz and Harry Vinall-Smeeth. A Dichotomy for Succinct Representations of Homomorphisms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 113:1-113:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.ICALP.2023.113,
  author =	{Berkholz, Christoph and Vinall-Smeeth, Harry},
  title =	{{A Dichotomy for Succinct Representations of Homomorphisms}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{113:1--113:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.113},
  URN =		{urn:nbn:de:0030-drops-181653},
  doi =		{10.4230/LIPIcs.ICALP.2023.113},
  annote =	{Keywords: homomorphism problem, CSP, succinct representations, enumeration, lower bound, treewidth}
}
  • Refine by Author
  • 1 Berkholz, Christoph
  • 1 Carmosino, Marco
  • 1 Fagin, Ronald
  • 1 Immerman, Neil
  • 1 Kolaitis, Phokion G.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Data compression
  • 1 Theory of computation → Data structures and algorithms for data management

  • Refine by Keyword
  • 1 Boolean functions
  • 1 CSP
  • 1 combinatorial games
  • 1 enumeration
  • 1 homomorphism problem
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2023
  • 1 2024

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 Imprint Privacy Contact