Kuan Cheng

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Streaming and small space approximation algorithms for edit distance and longest common subsequence	2026-05-12	Paper
\(\mathrm{BPL}\subseteq\mathrm{L}\text{-}\mathrm{AC}^1\)	2026-01-28	Paper
When can an expander code correct (n) errors in O(n) time? IEEE Transactions on Information Theory	2025-10-06	Paper
When can an expander code correct (n) errors in O(n) time?	2025-10-06	Paper
Randomness extractors in AC^0 and NC^1: optimal up to constant factors	2025-10-06	Paper
Exponential lower bounds for locally decodable and correctable codes for insertions and deletions	2025-08-13	Paper
Deterministic document exchange protocols, and almost optimal binary codes for edit errors	2025-08-12	Paper
On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction IEEE Transactions on Information Theory	2025-07-11	Paper
On relaxed locally decodable codes for Hamming and insertion-deletion errors	2024-11-19	Paper
Linear insertion deletion codes in the high-noise and high-rate regimes	2024-11-14	Paper
Random shortening of linear codes and applications	2024-08-22	Paper
Deterministic document exchange protocols and almost optimal binary codes for edit errors Journal of the ACM	2024-06-06	Paper
scientific article; zbMATH DE number 7788482 (Why is no real title available?) (available as arXiv preprint)	2024-01-15	Paper
scientific article; zbMATH DE number 7788339 (Why is no real title available?)	2024-01-15	Paper
Improved decoding of expander codes: fundamental trade-off between expansion ratio and minimum distance of inner code	2023-12-26	Paper
Random Shortening of Linear Codes and Applications	2023-08-30	Paper
Efficient Linear and Affine Codes for Correcting Insertions/Deletions SIAM Journal on Discrete Mathematics	2023-06-14	Paper
Hitting sets give two-sided derandomization of small space Theory of Computing	2022-10-18	Paper
Hitting sets give two-sided derandomization of small space	2022-07-21	Paper
scientific article; zbMATH DE number 7561530 (Why is no real title available?) (available as arXiv preprint)	2022-07-21	Paper
Randomness extraction in \(\mathsf{AC}^0\) and with small locality (available as arXiv preprint)	2021-08-04	Paper
Synchronization strings: highly efficient deterministic constructions over small alphabets Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-10-15	Paper
Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)	2018-01-19	Paper

Research outcomes over time

This page was built for person: Kuan Cheng