Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Lijie Chen, Ryan Williams, and Tianqi Yang. Black-Box Constructive Proofs Are Unavoidable. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ITCS.2023.35, author = {Chen, Lijie and Williams, Ryan and Yang, Tianqi}, title = {{Black-Box Constructive Proofs Are Unavoidable}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {35:1--35:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.35}, URN = {urn:nbn:de:0030-drops-175380}, doi = {10.4230/LIPIcs.ITCS.2023.35}, annote = {Keywords: Circuit lower bounds, natural proofs, probabilistic checkable proofs} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Lijie Chen, Jiatu Li, and Tianqi Yang. Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 23:1-23:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.CCC.2022.23, author = {Chen, Lijie and Li, Jiatu and Yang, Tianqi}, title = {{Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {23:1--23:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.23}, URN = {urn:nbn:de:0030-drops-165852}, doi = {10.4230/LIPIcs.CCC.2022.23}, annote = {Keywords: Almost universal hash functions, hardness magnification, pseudorandom functions} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Jonni Virtema, Jana Hofmann, Bernd Finkbeiner, Juha Kontinen, and Fan Yang. Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{virtema_et_al:LIPIcs.FSTTCS.2021.52, author = {Virtema, Jonni and Hofmann, Jana and Finkbeiner, Bernd and Kontinen, Juha and Yang, Fan}, title = {{Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {52:1--52:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.52}, URN = {urn:nbn:de:0030-drops-155634}, doi = {10.4230/LIPIcs.FSTTCS.2021.52}, annote = {Keywords: Linear temporal logic, Hyperproperties, Model Checking, Expressivity} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang. Counting of Teams in First-Order Team Logics. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haak_et_al:LIPIcs.MFCS.2019.19, author = {Haak, Anselm and Kontinen, Juha and M\"{u}ller, Fabian and Vollmer, Heribert and Yang, Fan}, title = {{Counting of Teams in First-Order Team Logics}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {19:1--19:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.19}, URN = {urn:nbn:de:0030-drops-109634}, doi = {10.4230/LIPIcs.MFCS.2019.19}, annote = {Keywords: team-based logics, counting classes, finite model theory, descriptive complexity} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Haitao Jiang, Chenglin Fan, Boting Yang, Farong Zhong, Daming Zhu, and Binhai Zhu. Genomic Scaffold Filling Revisited. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{jiang_et_al:LIPIcs.CPM.2016.15, author = {Jiang, Haitao and Fan, Chenglin and Yang, Boting and Zhong, Farong and Zhu, Daming and Zhu, Binhai}, title = {{Genomic Scaffold Filling Revisited}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.15}, URN = {urn:nbn:de:0030-drops-60791}, doi = {10.4230/LIPIcs.CPM.2016.15}, annote = {Keywords: Computational biology, Approximation algorithms, FPT algorithms, NP- completeness} }
Feedback for Dagstuhl Publishing