Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Eshan Chattopadhyay and Jyun-Jie Liao. Recursive Error Reduction for Regular Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2024.29, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Recursive Error Reduction for Regular Branching Programs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {29:1--29: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.29}, URN = {urn:nbn:de:0030-drops-195571}, doi = {10.4230/LIPIcs.ITCS.2024.29}, annote = {Keywords: read-once branching program, regular branching program, weighted pseudorandom generator, derandomization} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Lijie Chen, Xin Lyu, Avishay Tal, and Hongxun Wu. New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.39, author = {Chen, Lijie and Lyu, Xin and Tal, Avishay and Wu, Hongxun}, title = {{New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.39}, URN = {urn:nbn:de:0030-drops-180916}, doi = {10.4230/LIPIcs.ICALP.2023.39}, annote = {Keywords: pseudorandom generators, derandomization, read-once branching programs} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fu_et_al:LIPIcs.ICALP.2021.68, author = {Fu, Hu and Tang, Zhihao Gavin and Wu, Hongxun and Wu, Jinzhao and Zhang, Qianfan}, title = {{Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {68:1--68:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.68}, URN = {urn:nbn:de:0030-drops-141376}, doi = {10.4230/LIPIcs.ICALP.2021.68}, annote = {Keywords: Matching, Contention Resolution Scheme, Price of Information, Query-Commit} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ren:LIPIcs.ESA.2020.79, author = {Ren, Hanlin}, title = {{Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {79:1--79:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.79}, URN = {urn:nbn:de:0030-drops-129450}, doi = {10.4230/LIPIcs.ESA.2020.79}, annote = {Keywords: Graph theory, Failure-prone structures} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Hongxun Wu. Near-Optimal Algorithm for Constructing Greedy Consensus Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 105:1-105:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{wu:LIPIcs.ICALP.2020.105, author = {Wu, Hongxun}, title = {{Near-Optimal Algorithm for Constructing Greedy Consensus Tree}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {105:1--105:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.105}, URN = {urn:nbn:de:0030-drops-125122}, doi = {10.4230/LIPIcs.ICALP.2020.105}, annote = {Keywords: phylogenetic trees, greedy consensus trees, splay tree} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ran Duan, Ce Jin, and Hongxun Wu. Faster Algorithms for All Pairs Non-Decreasing Paths Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{duan_et_al:LIPIcs.ICALP.2019.48, author = {Duan, Ran and Jin, Ce and Wu, Hongxun}, title = {{Faster Algorithms for All Pairs Non-Decreasing Paths Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {48:1--48:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.48}, URN = {urn:nbn:de:0030-drops-106241}, doi = {10.4230/LIPIcs.ICALP.2019.48}, annote = {Keywords: graph optimization, matrix multiplication, non-decreasing paths} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Ce Jin and Hongxun Wu. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jin_et_al:OASIcs.SOSA.2019.17, author = {Jin, Ce and Wu, Hongxun}, title = {{A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {17:1--17:6}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.17}, URN = {urn:nbn:de:0030-drops-100436}, doi = {10.4230/OASIcs.SOSA.2019.17}, annote = {Keywords: subset sum, formal power series, FFT} }
Feedback for Dagstuhl Publishing