Xin Li

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 64

Top Topics

Improved Algorithm

Error Correcting

Highly Efficient

Top Venues

Electron. Colloquium Comput. Complex.

IACR Cryptol. ePrint Arch.

Publications

Xin Li, Yan Zhong
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. CCC (2024)
Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, Yu Zheng
Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes. ICALP (2023)
Xin Li
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. Electron. Colloquium Comput. Complex. (2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. CCC (2023)
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SIAM J. Discret. Math. 37 (2) (2023)
Xin Li, Yan Zhong
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. Electron. Colloquium Comput. Complex. (2023)
Xin Li, Yu Zheng
Streaming and Query Once Space Complexity of Longest Increasing Subsequence. CoRR (2023)
Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang
Improved Decoding of Expander Codes. IEEE Trans. Inf. Theory 69 (6) (2023)
Xue Chen, Kuan Cheng, Xin Li, Songtao Mao
Random Shortening of Linear Codes and Application. Electron. Colloquium Comput. Complex. (2023)
Xin Li, Shachar Lovett, Jiapeng Zhang
Sunflowers and Robust Sunflowers from Randomness Extractors. Theory Comput. 18 (2022)
Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang
Improved Decoding of Expander Codes. ITCS (2022)
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors. J. ACM 69 (6) (2022)
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João L. Ribeiro
Low-Degree Polynomials Extract From Local Sources. ICALP (2022)
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João L. Ribeiro
Low-Degree Polynomials Extract from Local Sources. CoRR (2022)
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João L. Ribeiro
Low-Degree Polynomials Extract from Local Sources. Electron. Colloquium Comput. Complex. (2022)
Kuan Cheng, Xin Li
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information. SODA (2021)
Xin Li, Yu Zheng
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence. FSTTCS (2021)
Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. ICALP (2021)
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SODA (2021)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
Extractors for adversarial sources via extremal hypergraphs. STOC (2020)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols. IACR Cryptol. ePrint Arch. 2020 (2020)
Kuan Cheng, Xin Li
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information. CoRR (2020)
Kuan Cheng, Xin Li, Yu Zheng
Locally Decodable Codes with Randomized Encoding. CoRR (2020)
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Nonmalleable Extractors and Codes, with Their Many Tampered Extensions. SIAM J. Comput. 49 (5) (2020)
Eshan Chattopadhyay, Xin Li
Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering. TCC (3) (2020)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols. Electron. Colloquium Comput. Complex. 27 (2020)
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. CoRR (2020)
Kuan Cheng, Zhengzhong Jin, Xin Li, Yu Zheng
Space Efficient Deterministic Approximation of String Measures. CoRR (2020)
Kuan Cheng, Xin Li, Yu Zheng
Locally Decodable Codes with Randomized Encoding. IACR Cryptol. ePrint Arch. 2020 (2020)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman
Extractors and Secret Sharing Against Bounded Collusion Protocols. FOCS (2020)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
Extractors for Adversarial Sources via Extremal Hypergraphs. Electron. Colloquium Comput. Complex. 26 (2019)
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. ICALP (2019)
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets. SODA (2019)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
Extractors for Adversarial Sources via Extremal Hypergraphs. IACR Cryptol. ePrint Arch. 2019 (2019)
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors. CoRR (2018)
Xin Li, Shachar Lovett, Jiapeng Zhang
Sunflowers and Quasi-Sunflowers from Randomness Extractors. APPROX-RANDOM (2018)
Eshan Chattopadhyay, Xin Li
Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More. IACR Cryptol. ePrint Arch. 2018 (2018)
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets. CoRR (2018)
Eshan Chattopadhyay, Xin Li
Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More. CoRR (2018)
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
A New Approach for Constructing Low-Error, Two-Source Extractors. Computational Complexity Conference (2018)
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors. FOCS (2018)
Xin Li, Shachar Lovett, Jiapeng Zhang
Sunflowers and Quasi-sunflowers from Randomness Extractors. Electron. Colloquium Comput. Complex. 25 (2018)
Eshan Chattopadhyay, Xin Li
Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More. Electron. Colloquium Comput. Complex. 25 (2018)
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
Edit Errors with Block Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. CoRR (2018)
Kuan Cheng, Xin Li
Randomness Extraction in AC0 and with Small Locality. APPROX-RANDOM (2018)
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate. Electron. Colloquium Comput. Complex. 24 (2017)
Kuan Cheng, Yuval Ishai, Xin Li
Near-Optimal Secret Sharing and Error Correcting Codes in AC0. IACR Cryptol. ePrint Arch. 2017 (2017)
Kuan Cheng, Xin Li, Ke Wu
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets. CoRR (2017)
Kuan Cheng, Yuval Ishai, Xin Li
Near-Optimal Secret Sharing and Error Correcting Codes in \mathsf AC^0 AC 0. TCC (2) (2017)
Eshan Chattopadhyay, Xin Li
Non-malleable codes and extractors for small-depth circuits, and affine functions. STOC (2017)
Kuan Cheng, Xin Li
and with Small Locality. Electron. Colloquium Comput. Complex. 23 (2016)
Xin Li
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors. Electron. Colloquium Comput. Complex. 23 (2016)
Kuan Cheng, Xin Li
Randomness Extraction in AC0 and with Small Locality. CoRR (2016)
Eshan Chattopadhyay, Xin Li
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. Electron. Colloquium Comput. Complex. 23 (2016)
Amitabh Basu, Michael Dinitz, Xin Li
Computing approximate PSD factorizations. CoRR (2016)
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Non-Malleable Extractors and Codes, with their Many Tampered Extensions. IACR Cryptol. ePrint Arch. 2016 (2016)
Eshan Chattopadhyay, Xin Li
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. CoRR (2016)
Xin Li
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors. CoRR (2016)
Eshan Chattopadhyay, Xin Li
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols. FOCS (2016)
Eshan Chattopadhyay, Xin Li
Extractors for sumset sources. STOC (2016)
Xin Li
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy. FOCS (2016)
Amitabh Basu, Michael Dinitz, Xin Li
Computing Approximate PSD Factorizations. APPROX-RANDOM (2016)
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Non-malleable extractors and codes, with their many tampered extensions. STOC (2016)
Eshan Chattopadhyay, Xin Li
Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions. Electron. Colloquium Comput. Complex. 23 (2016)
Xin Li
Three-Source Extractors for Polylogarithmic Min-Entropy. CoRR (2015)
Xin Li
Improved Constructions of Two-Source Extractors. Electron. Colloquium Comput. Complex. 22 (2015)
Xin Li
Extractors for Affine Sources with Polylogarithmic Entropy. Electron. Colloquium Comput. Complex. 22 (2015)
Xin Li
Three-Source Extractors for Polylogarithmic Min-Entropy. FOCS (2015)
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Non-Malleable Extractors and Codes, with their Many Tampered Extensions. Electron. Colloquium Comput. Complex. 22 (2015)
Xin Li
Three-Source Extractors for Polylogarithmic Min-Entropy. Electron. Colloquium Comput. Complex. 22 (2015)
Xin Li
Non-malleable Condensers for Arbitrary Min-entropy, and Almost Optimal Protocols for Privacy Amplification. TCC (1) (2015)
Eshan Chattopadhyay, Xin Li
Extractors for Sumset Sources. Electron. Colloquium Comput. Complex. 22 (2015)
Xin Li
Improved Constructions of Two-Source Extractors. CoRR (2015)
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Non-Malleable Extractors and Codes, with their Many Tampered Extensions. CoRR (2015)
Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman
Privacy Amplification and Nonmalleable Extractors Via Character Sums. SIAM J. Comput. 43 (2) (2014)
Kai-Min Chung, Xin Li, Xiaodi Wu
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. CoRR (2014)
Kai-Min Chung, Xin Li, Xiaodi Wu
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. Electron. Colloquium Comput. Complex. 21 (2014)
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Robust Pseudorandom Generators. ICALP (1) (2013)
Xin Li
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. Electron. Colloquium Comput. Complex. 20 (2013)
Xin Li
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. FOCS (2013)
Xin Li
New independent source extractors with exponential improvement. STOC (2013)
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Robust Pseudorandom Generators. IACR Cryptol. ePrint Arch. 2013 (2013)
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Robust Pseudorandom Generators. Electron. Colloquium Comput. Complex. 20 (2013)
Xin Li
Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification. IACR Cryptol. ePrint Arch. 2012 (2012)
Xin Li
Design extractors, non-malleable condensers and privacy amplification. STOC (2012)
Xin Li
New Independent Source Extractors with Exponential Improvement. Electron. Colloquium Comput. Complex. 19 (2012)
Xin Li
Non-malleable Extractors, Two-Source Extractors and Privacy Amplification. FOCS (2012)
Xin Li
Non-Malleable Extractors for Entropy Rate <1/2 CoRR (2011)
Xin Li
Non-Malleable Extractors for Entropy Rate <1/2. Electron. Colloquium Comput. Complex. 18 (2011)
Xin Li
Improved Constructions of Three Source Extractors. Computational Complexity Conference (2011)
Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman
Privacy Amplification and Non-malleable Extractors via Character Sums. FOCS (2011)
Xin Li
Design Extractors, Non-Malleable Condensers and Privacy Amplification. Electron. Colloquium Comput. Complex. 18 (2011)
Xin Li
A New Approach to Affine Extractors and Dispersers. Computational Complexity Conference (2011)
Xin Li
A New Approach to Affine Extractors and Dispersers. Electron. Colloquium Comput. Complex. 17 (2010)
Xin Li
Improved Constructions of Three Source Extractors. Electron. Colloquium Comput. Complex. 17 (2010)
Xin Li
On the Problem of Local Randomness in Privacy Amplification with an Active Adversary CoRR (2010)
Yael Tauman Kalai, Xin Li, Anup Rao
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness. FOCS (2009)
Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman
Network Extractor Protocols. FOCS (2008)
Xin Li, Luo Sun, Linmi Tao, Guangyou Xu, Ying Jia
A Speaker Tracking Algorithm Based on Audio and Visual Information Fusion Using Particle Filter. ICIAR (2) (2004)