Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 29:1-29:56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2024.29, author = {Hirahara, Shuichi and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {29:1--29:56}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.29}, URN = {urn:nbn:de:0030-drops-204256}, doi = {10.4230/LIPIcs.CCC.2024.29}, annote = {Keywords: average-case complexity, Kolmogorov complexity, search-to-decision reductions} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
G. A. Kavvos. Two-Dimensional Kripke Semantics I: Presheaves. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kavvos:LIPIcs.FSCD.2024.14, author = {Kavvos, G. A.}, title = {{Two-Dimensional Kripke Semantics I: Presheaves}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {14:1--14:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.14}, URN = {urn:nbn:de:0030-drops-203438}, doi = {10.4230/LIPIcs.FSCD.2024.14}, annote = {Keywords: modal logic, categorical semantics, Kripke semantics, duality, open maps} }
Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)
James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{delgrande_et_al:DagMan.10.1.1, author = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, title = {{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}}, pages = {1--61}, journal = {Dagstuhl Manifestos}, ISSN = {2193-2433}, year = {2024}, volume = {10}, number = {1}, editor = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1}, URN = {urn:nbn:de:0030-drops-201403}, doi = {10.4230/DagMan.10.1.1}, annote = {Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal. Semantic Web: Past, Present, and Future. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 3:1-3:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{scherp_et_al:TGDK.2.1.3, author = {Scherp, Ansgar and Groener, Gerd and \v{S}koda, Petr and Hose, Katja and Vidal, Maria-Esther}, title = {{Semantic Web: Past, Present, and Future}}, journal = {Transactions on Graph Data and Knowledge}, pages = {3:1--3:37}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.3}, URN = {urn:nbn:de:0030-drops-198607}, doi = {10.4230/TGDK.2.1.3}, annote = {Keywords: Linked Open Data, Semantic Web Graphs, Knowledge Graphs} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119, author = {van Melkebeek, Dieter and Morgan, Andrew}, title = {{Polynomial Identity Testing via Evaluation of Rational Functions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {119:1--119:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119}, URN = {urn:nbn:de:0030-drops-157158}, doi = {10.4230/LIPIcs.ITCS.2022.119}, annote = {Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.ISAAC.2021.54, author = {Allender, Eric and Gouwar, John and Hirahara, Shuichi and Robelle, Caleb}, title = {{Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.54}, URN = {urn:nbn:de:0030-drops-154875}, doi = {10.4230/LIPIcs.ISAAC.2021.54}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs, Minimum Circuit Size Problem, Worst-case to Average-case Reductions} }
Published in: Dagstuhl Reports, Volume 9, Issue 9 (2020)
Jo Ellis-Monaghan, Andrew Goodall, Iain Moffatt, and Kerri Morgan. Comparative Theory for Graph Polynomials (Dagstuhl Seminar 19401). In Dagstuhl Reports, Volume 9, Issue 9, pp. 135-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Article{ellismonaghan_et_al:DagRep.9.9.135, author = {Ellis-Monaghan, Jo and Goodall, Andrew and Moffatt, Iain and Morgan, Kerri}, title = {{Comparative Theory for Graph Polynomials (Dagstuhl Seminar 19401)}}, pages = {135--155}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2020}, volume = {9}, number = {9}, editor = {Ellis-Monaghan, Jo and Goodall, Andrew and Moffatt, Iain and Morgan, Kerri}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.9.135}, URN = {urn:nbn:de:0030-drops-118460}, doi = {10.4230/DagRep.9.9.135}, annote = {Keywords: graph polynomials, graph and matroid invariants, Tutte polynomial, topological and algebraic graph theory} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Evan Cavallo, Anders Mörtberg, and Andrew W Swan. Unifying Cubical Models of Univalent Type Theory. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cavallo_et_al:LIPIcs.CSL.2020.14, author = {Cavallo, Evan and M\"{o}rtberg, Anders and Swan, Andrew W}, title = {{Unifying Cubical Models of Univalent Type Theory}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {14:1--14:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel 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.CSL.2020.14}, URN = {urn:nbn:de:0030-drops-116578}, doi = {10.4230/LIPIcs.CSL.2020.14}, annote = {Keywords: Cubical Set Models, Cubical Type Theory, Homotopy Type Theory, Univalent Foundations} }
Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)
Robert Sison and Toby Murray. Verifying That a Compiler Preserves Concurrent Value-Dependent Information-Flow Security. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sison_et_al:LIPIcs.ITP.2019.27, author = {Sison, Robert and Murray, Toby}, title = {{Verifying That a Compiler Preserves Concurrent Value-Dependent Information-Flow Security}}, booktitle = {10th International Conference on Interactive Theorem Proving (ITP 2019)}, pages = {27:1--27:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-122-1}, ISSN = {1868-8969}, year = {2019}, volume = {141}, editor = {Harrison, John and O'Leary, John and Tolmach, Andrew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.27}, URN = {urn:nbn:de:0030-drops-110829}, doi = {10.4230/LIPIcs.ITP.2019.27}, annote = {Keywords: Secure compilation, Information flow security, Concurrency, Verification} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20, author = {Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew}, title = {{Minimum Circuit Size, Graph Isomorphism, and Related Problems}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20}, URN = {urn:nbn:de:0030-drops-83455}, doi = {10.4230/LIPIcs.ITCS.2018.20}, annote = {Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity} }