OASIcs, Volume 97
Tokenomics 2021, November 18-19, 2021, New York University, USA (Virtual Conference)
Editors: Vincent Gramoli, Hanna Halaburda, and Rafael Pass
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Graham Cormode, Marcel Dall'Agnol, Tom Gur, and Chris Hickey. Streaming Zero-Knowledge Proofs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 2:1-2:66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cormode_et_al:LIPIcs.CCC.2024.2, author = {Cormode, Graham and Dall'Agnol, Marcel and Gur, Tom and Hickey, Chris}, title = {{Streaming Zero-Knowledge Proofs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {2:1--2:66}, 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.2}, URN = {urn:nbn:de:0030-drops-203988}, doi = {10.4230/LIPIcs.CCC.2024.2}, annote = {Keywords: Zero-knowledge proofs, streaming algorithms, computational complexity} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Justin Holmgren and Ron Rothblum. Linear-Size Boolean Circuits for Multiselection. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{holmgren_et_al:LIPIcs.CCC.2024.11, author = {Holmgren, Justin and Rothblum, Ron}, title = {{Linear-Size Boolean Circuits for Multiselection}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {11:1--11:20}, 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.11}, URN = {urn:nbn:de:0030-drops-204070}, doi = {10.4230/LIPIcs.CCC.2024.11}, annote = {Keywords: Private Information Retrieval, Batch Selection, Boolean Circuits} }
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 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Search-To-Decision Reductions for Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.34, author = {Mazor, Noam and Pass, Rafael}, title = {{Search-To-Decision Reductions for Kolmogorov Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {34:1--34:20}, 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.34}, URN = {urn:nbn:de:0030-drops-204308}, doi = {10.4230/LIPIcs.CCC.2024.34}, annote = {Keywords: Kolmogorov complexity, search to decision} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36, author = {Mazor, Noam and Pass, Rafael}, title = {{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {36:1--36:21}, 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.36}, URN = {urn:nbn:de:0030-drops-204322}, doi = {10.4230/LIPIcs.CCC.2024.36}, annote = {Keywords: Kolmogorov complexity, MCSP, Levin Reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Zhenjian Lu and Rahul Santhanam. Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lu_et_al:LIPIcs.ICALP.2024.110, author = {Lu, Zhenjian and Santhanam, Rahul}, title = {{Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {110:1--110:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.110}, URN = {urn:nbn:de:0030-drops-202538}, doi = {10.4230/LIPIcs.ICALP.2024.110}, annote = {Keywords: meta-complexity, Kolmogorov complexity, one-way functions, average-case complexity} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Noam Mazor and Rafael Pass. The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.ITCS.2024.80, author = {Mazor, Noam and Pass, Rafael}, title = {{The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {80:1--80:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.80}, URN = {urn:nbn:de:0030-drops-196088}, doi = {10.4230/LIPIcs.ITCS.2024.80}, annote = {Keywords: Kolmogorov complexity, perebor conjecture, function inversion} }
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: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)
3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 1-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{gramoli_et_al:OASIcs.Tokenomics.2021, title = {{OASIcs, Volume 97, Tokenomics 2021, Complete Volume}}, booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)}, pages = {1--124}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-220-4}, ISSN = {2190-6807}, year = {2022}, volume = {97}, editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021}, URN = {urn:nbn:de:0030-drops-158965}, doi = {10.4230/OASIcs.Tokenomics.2021}, annote = {Keywords: OASIcs, Volume 97, Tokenomics 2021, Complete Volume} }
Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)
3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gramoli_et_al:OASIcs.Tokenomics.2021.0, author = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)}, pages = {0:i--0:x}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-220-4}, ISSN = {2190-6807}, year = {2022}, volume = {97}, editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.0}, URN = {urn:nbn:de:0030-drops-158975}, doi = {10.4230/OASIcs.Tokenomics.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)
Joseph Y. Halpern. Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk (Invited Talk). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{halpern:OASIcs.Tokenomics.2021.1, author = {Halpern, Joseph Y.}, title = {{Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk}}, booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)}, pages = {1:1--1:2}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-220-4}, ISSN = {2190-6807}, year = {2022}, volume = {97}, editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.1}, URN = {urn:nbn:de:0030-drops-158981}, doi = {10.4230/OASIcs.Tokenomics.2021.1}, annote = {Keywords: robust equilibrium, implementing mediators, asynchronous systems} }
Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)
Zhichun Lu, Runchao Han, and Jiangshan Yu. General Congestion Attack on HTLC-Based Payment Channel Networks. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lu_et_al:OASIcs.Tokenomics.2021.2, author = {Lu, Zhichun and Han, Runchao and Yu, Jiangshan}, title = {{General Congestion Attack on HTLC-Based Payment Channel Networks}}, booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)}, pages = {2:1--2:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-220-4}, ISSN = {2190-6807}, year = {2022}, volume = {97}, editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.2}, URN = {urn:nbn:de:0030-drops-158990}, doi = {10.4230/OASIcs.Tokenomics.2021.2}, annote = {Keywords: Blockchain, PCN, Congestion} }