Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)
Yiming Xu and Michael Norrish. Dependently Sorted Theorem Proving for Mathematical Foundations. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{xu_et_al:LIPIcs.ITP.2023.33, author = {Xu, Yiming and Norrish, Michael}, title = {{Dependently Sorted Theorem Proving for Mathematical Foundations}}, booktitle = {14th International Conference on Interactive Theorem Proving (ITP 2023)}, pages = {33:1--33:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-284-6}, ISSN = {1868-8969}, year = {2023}, volume = {268}, editor = {Naumowicz, Adam and Thiemann, Ren\'{e}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.33}, URN = {urn:nbn:de:0030-drops-184085}, doi = {10.4230/LIPIcs.ITP.2023.33}, annote = {Keywords: first order logic, sorts, structural set theory, mechanised mathematics, foundation of mathematics, category theory} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
James Worrell. The Skolem Landscape (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{worrell:LIPIcs.ICALP.2023.5, author = {Worrell, James}, title = {{The Skolem Landscape}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {5:1--5:2}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.5}, URN = {urn:nbn:de:0030-drops-180573}, doi = {10.4230/LIPIcs.ICALP.2023.5}, annote = {Keywords: Automata, Formal Languages, Linear Recurrence Sequences} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dcosta_et_al:LIPIcs.MFCS.2021.33, author = {D'Costa, Julian and Lefaucheux, Engel and Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James}, title = {{On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {33:1--33:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.33}, URN = {urn:nbn:de:0030-drops-144734}, doi = {10.4230/LIPIcs.MFCS.2021.33}, annote = {Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Theory of the reals} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Joshua A. Grochow and Youming Qiao. On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grochow_et_al:LIPIcs.CCC.2021.16, author = {Grochow, Joshua A. and Qiao, Youming}, title = {{On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {16:1--16:38}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.16}, URN = {urn:nbn:de:0030-drops-142905}, doi = {10.4230/LIPIcs.CCC.2021.16}, annote = {Keywords: group isomorphism, search-to-decision reduction, counting-to-decision reduction, nilpotent group isomorphism, p-group isomorphism, tensor isomorphism} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Andrew M. Childs, Shih-Han Hung, and Tongyang Li. Quantum Query Complexity with Matrix-Vector Products. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{childs_et_al:LIPIcs.ICALP.2021.55, author = {Childs, Andrew M. and Hung, Shih-Han and Li, Tongyang}, title = {{Quantum Query Complexity with Matrix-Vector Products}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.55}, URN = {urn:nbn:de:0030-drops-141242}, doi = {10.4230/LIPIcs.ICALP.2021.55}, annote = {Keywords: Quantum algorithms, quantum query complexity, matrix-vector products} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum Algorithms for Matrix Scaling and Matrix Balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2021.110, author = {van Apeldoorn, Joran and Gribling, Sander and Li, Yinan and Nieuwboer, Harold and Walter, Michael and de Wolf, Ronald}, title = {{Quantum Algorithms for Matrix Scaling and Matrix Balancing}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {110:1--110:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.110}, URN = {urn:nbn:de:0030-drops-141793}, doi = {10.4230/LIPIcs.ICALP.2021.110}, annote = {Keywords: Matrix scaling, matrix balancing, quantum algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Bounded Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 127:1-127:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{colcombet_et_al:LIPIcs.ICALP.2021.127, author = {Colcombet, Thomas and Jaquard, Arthur}, title = {{A Complexity Approach to Tree Algebras: the Bounded Case}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {127:1--127:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.127}, URN = {urn:nbn:de:0030-drops-141966}, doi = {10.4230/LIPIcs.ICALP.2021.127}, annote = {Keywords: Tree algebra, infinite tree, language theory} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dominik D. Freydenberger and Liat Peterfreund. The Theory of Concatenation over Finite Models. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 130:1-130:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{freydenberger_et_al:LIPIcs.ICALP.2021.130, author = {Freydenberger, Dominik D. and Peterfreund, Liat}, title = {{The Theory of Concatenation over Finite Models}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {130:1--130:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.130}, URN = {urn:nbn:de:0030-drops-141997}, doi = {10.4230/LIPIcs.ICALP.2021.130}, annote = {Keywords: finite model theory, word equations, descriptive complexity, model checking, document spanners} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Martin Hoefer, Pasin Manurangsi, and Alexandros Psomas. Algorithmic Persuasion with Evidence. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoefer_et_al:LIPIcs.ITCS.2021.3, author = {Hoefer, Martin and Manurangsi, Pasin and Psomas, Alexandros}, title = {{Algorithmic Persuasion with Evidence}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.3}, URN = {urn:nbn:de:0030-drops-135420}, doi = {10.4230/LIPIcs.ITCS.2021.3}, annote = {Keywords: Bayesian Persuasion, Semidefinite Programming, Approximation Algorithms} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhattacharya_et_al:LIPIcs.ITCS.2021.15, author = {Bhattacharya, Anup and Bishnu, Arijit and Mishra, Gopinath and Upasana, Anannya}, title = {{Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.15}, URN = {urn:nbn:de:0030-drops-135544}, doi = {10.4230/LIPIcs.ITCS.2021.15}, annote = {Keywords: Streaming, random ordering, graph coloring, estimation, lower bounds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Geoffroy Couteau, Pooya Farshim, and Mohammad Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{couteau_et_al:LIPIcs.ITCS.2021.47, author = {Couteau, Geoffroy and Farshim, Pooya and Mahmoody, Mohammad}, title = {{Black-Box Uselessness: Composing Separations in Cryptography}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {47:1--47:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.47}, URN = {urn:nbn:de:0030-drops-135869}, doi = {10.4230/LIPIcs.ITCS.2021.47}, annote = {Keywords: Black-Box Reductions, Separations, One-Way Functions, Key Agreement} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Vijay V. Vazirani and Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vazirani_et_al:LIPIcs.ITCS.2021.59, author = {Vazirani, Vijay V. and Yannakakis, Mihalis}, title = {{Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {59:1--59:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.59}, URN = {urn:nbn:de:0030-drops-135987}, doi = {10.4230/LIPIcs.ITCS.2021.59}, annote = {Keywords: Hyland-Zeckhauser scheme, one-sided matching markets, mechanism design, dichotomous utilities, PPAD, FIXP} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Quantitative Correlation Inequalities via Semigroup Interpolation. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{de_et_al:LIPIcs.ITCS.2021.69, author = {De, Anindya and Nadimpalli, Shivam and Servedio, Rocco A.}, title = {{Quantitative Correlation Inequalities via Semigroup Interpolation}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {69:1--69:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.69}, URN = {urn:nbn:de:0030-drops-136081}, doi = {10.4230/LIPIcs.ITCS.2021.69}, annote = {Keywords: complex analysis, correlation inequality, FKG inequality, Gaussian correlation inequality, harmonic analysis, Markov semigroups} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson. Message Complexity of Population Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{amir_et_al:LIPIcs.DISC.2020.6, author = {Amir, Talley and Aspnes, James and Doty, David and Eftekhari, Mahsa and Severson, Eric}, title = {{Message Complexity of Population Protocols}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.6}, URN = {urn:nbn:de:0030-drops-130848}, doi = {10.4230/LIPIcs.DISC.2020.6}, annote = {Keywords: population protocol, message complexity, space-optimal} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues. On Polynomial Recursive Sequences. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 117:1-117:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cadilhac_et_al:LIPIcs.ICALP.2020.117, author = {Cadilhac, Micha\"{e}l and Mazowiecki, Filip and Paperman, Charles and Pilipczuk, Micha{\l} and S\'{e}nizergues, G\'{e}raud}, title = {{On Polynomial Recursive Sequences}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {117:1--117:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.117}, URN = {urn:nbn:de:0030-drops-125240}, doi = {10.4230/LIPIcs.ICALP.2020.117}, annote = {Keywords: recursive sequences, expressive power, weighted automata, higher-order pushdown automata} }
Feedback for Dagstuhl Publishing