Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
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)
@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} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
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)
@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} }
Feedback for Dagstuhl Publishing