Xin Li

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