Kuan Cheng

According to our database, Kuan Cheng authored at least 31 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

$BPL\subseteq L-AC^1$.

Kuan Cheng, Yichuan Wang

Electron. Colloquium Comput. Complex., 2024

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors.

Kuan Cheng, Ruiyang Wu

Electron. Colloquium Comput. Complex., 2024

2023

Improved Decoding of Expander Codes.

Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang

IEEE Trans. Inf. Theory, June, 2023

Efficient Linear and Affine Codes for Correcting Insertions/Deletions.

Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li

SIAM J. Discret. Math., June, 2023

Random Shortening of Linear Codes and Application.

Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Electron. Colloquium Comput. Complex., 2023

Improved decoding of expander codes: fundamental trade-off between expansion ratio and minimum distance of inner code.

Kuan Cheng, Minghui Ouyang, Chong Shangguan, Yuanting Shen

CoRR, 2023

FreeKD: Knowledge Distillation via Semantic Frequency Prompt.

Yuan Zhang, Tao Huang, Jiaming Liu, Tao Jiang, Kuan Cheng, Shanghang Zhang

CoRR, 2023

On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction.

Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu

CoRR, 2023

On The Relative Error of Random Fourier Features for Preserving Kernel Distance.

Kuan Cheng, Shaofeng H.-C. Jiang, Luojian Wei, Zhide Wei

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes.

Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, Yu Zheng

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Random Shortening of Linear Codes and Applications.

Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors.

Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Hitting Sets Give Two-Sided Derandomization of Small Space.

Kuan Cheng, William M. Hoza

Theory Comput., 2022

Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu

J. ACM, 2022

2021

Efficient Document Exchange and Error Correcting Codes with Asymmetric Information.

Kuan Cheng, Xin Li

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.

Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions.

Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Locally Decodable Codes with Randomized Encoding.

Kuan Cheng, Xin Li, Yu Zheng

IACR Cryptol. ePrint Arch., 2020

Space Efficient Deterministic Approximation of String Measures.

Kuan Cheng, Zhengzhong Jin, Xin Li, Yu Zheng

CoRR, 2020

2019

Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.

Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Edit Errors with Block Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu

CoRR, 2018

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.

Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu

CoRR, 2018

Randomness Extraction in AC0 and with Small Locality.

Kuan Cheng, Xin Li

Proceedings of the Approximation, 2018

2017

Cold Centering Algorithm on Pipe Based on Laser Measurement.

Yongbo Li, Xiandong Yin, Weiling Liu, Yafeng Liu, Weihan Gou, Kuan Cheng

J. Adv. Comput. Intell. Intell. Informatics, 2017

Near-Optimal Secret Sharing and Error Correcting Codes in AC0.

Kuan Cheng, Yuval Ishai, Xin Li

IACR Cryptol. ePrint Arch., 2017

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.

Kuan Cheng, Xin Li, Ke Wu

CoRR, 2017

Near-Optimal Secret Sharing and Error Correcting Codes in \mathsf AC^0 AC 0.

Kuan Cheng, Yuval Ishai, Xin Li

Proceedings of the Theory of Cryptography - 15th International Conference, 2017

2016

Randomness Extraction in AC⁰ and with Small Locality.

Kuan Cheng, Xin Li

Electron. Colloquium Comput. Complex., 2016

2014

Pseudorandom Generator Based on Hard Lattice Problem.

Kuan Cheng

IACR Cryptol. ePrint Arch., 2014

2013

Some Improved Complexity Results for uSVP and GapSVP.

Kuan Cheng

IACR Cryptol. ePrint Arch., 2013