Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{block_et_al:LIPIcs.CCC.2023.14, author = {Block, Alexander R. and Blocki, Jeremiah and Cheng, Kuan and Grigorescu, Elena and Li, Xin and Zheng, Yu and Zhu, Minshen}, title = {{On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {14:1--14:25}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.14}, URN = {urn:nbn:de:0030-drops-182847}, doi = {10.4230/LIPIcs.CCC.2023.14}, annote = {Keywords: Relaxed Locally Decodable Codes, Hamming Errors, Insdel Errors, Lower Bounds} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, and Yu Zheng. Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheng_et_al:LIPIcs.ICALP.2023.41, author = {Cheng, Kuan and Jin, Zhengzhong and Li, Xin and Wei, Zhide and Zheng, Yu}, title = {{Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {41:1--41:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.41}, URN = {urn:nbn:de:0030-drops-180931}, doi = {10.4230/LIPIcs.ICALP.2023.41}, annote = {Keywords: Error correcting code, Edit distance, Pseudorandomness, Derandomization} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved Decoding of Expander Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.43, author = {Chen, Xue and Cheng, Kuan and Li, Xin and Ouyang, Minghui}, title = {{Improved Decoding of Expander Codes}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {43:1--43:3}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.43}, URN = {urn:nbn:de:0030-drops-156394}, doi = {10.4230/LIPIcs.ITCS.2022.43}, annote = {Keywords: Expander Code, Decoding} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Xin Li and Yu Zheng. Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence. 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. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{li_et_al:LIPIcs.FSTTCS.2021.27, author = {Li, Xin and Zheng, Yu}, title = {{Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {27:1--27:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.27}, URN = {urn:nbn:de:0030-drops-155381}, doi = {10.4230/LIPIcs.FSTTCS.2021.27}, annote = {Keywords: Asymmetric Streaming Model, Edit Distance, Longest Common Subsequence, Space Lower Bound} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, and Yu Zheng. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheng_et_al:LIPIcs.ICALP.2021.54, author = {Cheng, Kuan and Farhadi, Alireza and Hajiaghayi, MohammadTaghi and Jin, Zhengzhong and Li, Xin and Rubinstein, Aviad and Seddighin, Saeed and Zheng, Yu}, title = {{Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {54:1--54: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.54}, URN = {urn:nbn:de:0030-drops-141236}, doi = {10.4230/LIPIcs.ICALP.2021.54}, annote = {Keywords: Edit Distance, Longest Common Subsequence, Longest Increasing Subsequence, Space Efficient Algorithm, Approximation Algorithm} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26, author = {Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu}, title = {{Elder-Rule-Staircodes for Augmented Metric Spaces}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.26}, URN = {urn:nbn:de:0030-drops-121848}, doi = {10.4230/LIPIcs.SoCG.2020.26}, annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Simon Zhang, Mengbai Xiao, and Hao Wang. GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{zhang_et_al:LIPIcs.SoCG.2020.70, author = {Zhang, Simon and Xiao, Mengbai and Wang, Hao}, title = {{GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {70:1--70:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.70}, URN = {urn:nbn:de:0030-drops-122287}, doi = {10.4230/LIPIcs.SoCG.2020.70}, annote = {Keywords: Parallel Algorithms, Topological Data Analysis, Vietoris-Rips, Persistent Homology, Apparent Pairs, High Performance Computing, GPU, Random Graphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu. Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cheng_et_al:LIPIcs.ICALP.2019.37, author = {Cheng, Kuan and Jin, Zhengzhong and Li, Xin and Wu, Ke}, title = {{Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {37:1--37:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.37}, URN = {urn:nbn:de:0030-drops-106137}, doi = {10.4230/LIPIcs.ICALP.2019.37}, annote = {Keywords: Deterministic document exchange, error correcting code, block edit error} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Kuan Cheng and Xin Li. Randomness Extraction in AC0 and with Small Locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cheng_et_al:LIPIcs.APPROX-RANDOM.2018.37, author = {Cheng, Kuan and Li, Xin}, title = {{Randomness Extraction in AC0 and with Small Locality}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {37:1--37:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.37}, URN = {urn:nbn:de:0030-drops-94414}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.37}, annote = {Keywords: Randomness Extraction, AC0, Locality, Pseudorandom Generator} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Tamal K. Dey and Cheng Xin. Computing Bottleneck Distance for 2-D Interval Decomposable Modules. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dey_et_al:LIPIcs.SoCG.2018.32, author = {Dey, Tamal K. and Xin, Cheng}, title = {{Computing Bottleneck Distance for 2-D Interval Decomposable Modules}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {32:1--32:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.32}, URN = {urn:nbn:de:0030-drops-87453}, doi = {10.4230/LIPIcs.SoCG.2018.32}, annote = {Keywords: Persistence modules, bottleneck distance, interleaving distance} }
Feedback for Dagstuhl Publishing