Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Yanyi Liu and Rafael Pass. Leakage-Resilient Hardness vs Randomness. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 32:1-32:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{liu_et_al:LIPIcs.CCC.2023.32, author = {Liu, Yanyi and Pass, Rafael}, title = {{Leakage-Resilient Hardness vs Randomness}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {32:1--32:20}, 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.32}, URN = {urn:nbn:de:0030-drops-183022}, doi = {10.4230/LIPIcs.CCC.2023.32}, annote = {Keywords: Derandomization, Leakage-Resilient Hardness} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Yanyi Liu and Rafael Pass. Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 35:1-35:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{liu_et_al:LIPIcs.CCC.2022.35, author = {Liu, Yanyi and Pass, Rafael}, title = {{Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {35:1--35:17}, 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.35}, URN = {urn:nbn:de:0030-drops-165975}, doi = {10.4230/LIPIcs.CCC.2022.35}, annote = {Keywords: Derandomization, Kolmogorov Complexity, Hitting Set Generators} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Yanyi Liu and Rafael Pass. On One-Way Functions from NP-Complete Problems. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 36:1-36:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{liu_et_al:LIPIcs.CCC.2022.36, author = {Liu, Yanyi and Pass, Rafael}, title = {{On One-Way Functions from NP-Complete Problems}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {36:1--36:24}, 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.36}, URN = {urn:nbn:de:0030-drops-165981}, doi = {10.4230/LIPIcs.CCC.2022.36}, annote = {Keywords: One-way Functions, NP-Completeness, Kolmogorov Complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chia_et_al:LIPIcs.ITCS.2022.47, author = {Chia, Nai-Hui and Chou, Chi-Ning and Zhang, Jiayu and Zhang, Ruizhe}, title = {{Quantum Meets the Minimum Circuit Size Problem}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {47:1--47:16}, 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.47}, URN = {urn:nbn:de:0030-drops-156433}, doi = {10.4230/LIPIcs.ITCS.2022.47}, annote = {Keywords: Quantum Computation, Quantum Complexity, Minimum Circuit Size Problem} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-Way Functions and a Conditional Variant of MKTP. 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. 7:1-7:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.FSTTCS.2021.7, author = {Allender, Eric and Cheraghchi, Mahdi and Myrisiotis, Dimitrios and Tirumala, Harsha and Volkovich, Ilya}, title = {{One-Way Functions and a Conditional Variant of MKTP}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {7:1--7:19}, 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.7}, URN = {urn:nbn:de:0030-drops-155181}, doi = {10.4230/LIPIcs.FSTTCS.2021.7}, annote = {Keywords: Kolmogorov complexity, KT Complexity, Minimum KT-complexity Problem, MKTP, Conditional KT Complexity, Minimum Conditional KT-complexity Problem, McKTP, one-way functions, OWFs, average-case hardness, pseudorandom generators, PRGs, pseudorandom functions, PRFs, distinguishers, learning algorithms, NP-completeness, reductions} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 35:1-35:58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ren_et_al:LIPIcs.CCC.2021.35, author = {Ren, Hanlin and Santhanam, Rahul}, title = {{Hardness of KT Characterizes Parallel Cryptography}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {35:1--35:58}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.35}, URN = {urn:nbn:de:0030-drops-143091}, doi = {10.4230/LIPIcs.CCC.2021.35}, annote = {Keywords: one-way function, meta-complexity, KT complexity, parallel cryptography, randomized encodings} }
Feedback for Dagstuhl Publishing