Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Improved Learning from Kolmogorov Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {12:1--12:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.12}, URN = {urn:nbn:de:0030-drops-182825}, doi = {10.4230/LIPIcs.CCC.2023.12}, annote = {Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Rahul Santhanam. An Algorithmic Approach to Uniform Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 35:1-35:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{santhanam:LIPIcs.CCC.2023.35, author = {Santhanam, Rahul}, title = {{An Algorithmic Approach to Uniform Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {35:1--35:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.35}, URN = {urn:nbn:de:0030-drops-183053}, doi = {10.4230/LIPIcs.CCC.2023.35}, annote = {Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16, author = {Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {16:1--16:60}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16}, URN = {urn:nbn:de:0030-drops-165785}, doi = {10.4230/LIPIcs.CCC.2022.16}, annote = {Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 92:1-92:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lu_et_al:LIPIcs.ICALP.2022.92, author = {Lu, Zhenjian and Oliveira, Igor C. and Zimand, Marius}, title = {{Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {92:1--92:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.92}, URN = {urn:nbn:de:0030-drops-164331}, doi = {10.4230/LIPIcs.ICALP.2022.92}, annote = {Keywords: computational complexity, randomized algorithms, Kolmogorov complexity} }
Feedback for Dagstuhl Publishing