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.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.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.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 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.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 169, 35th Computational Complexity Conference (CCC 2020)
Kuan Cheng and William M. Hoza. Hitting Sets Give Two-Sided Derandomization of Small Space. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cheng_et_al:LIPIcs.CCC.2020.10, author = {Cheng, Kuan and Hoza, William M.}, title = {{Hitting Sets Give Two-Sided Derandomization of Small Space}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {10:1--10:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.10}, URN = {urn:nbn:de:0030-drops-125625}, doi = {10.4230/LIPIcs.CCC.2020.10}, annote = {Keywords: hitting sets, derandomization, read-once branching programs} }
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.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.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} }
Feedback for Dagstuhl Publishing