Welcome to Xin Li's Homepage!
I am an Associate Professor in the
Computer Science Department
of the Whiting School of Engineering
at
Johns Hopkins University.
I am a member of the theory group.
Contact:
Email: lixints@cs.jhu.edu
Office: Malone Hall 215
Postal: Department of Computer Science
Johns Hopkins University
3400 N. Charles St.
Baltimore, MD 21218
Research
I am broadly interested in theory of computation. Especially, I am interested in the use of randomness in computation, complexity theory, coding theory, and cryptography. A significant part of my previous work has been on explicit constructions of randomness extractors. For example, I have made key contributions in the recent line of research that has resulted in an almost optimal solution to the long standing open problem of constructing explicit two source extractors. See here for a briefy history of this problem.
I obtained my Ph.D. degree from University of Texas at Austin in 2011, under the supervison of David Zuckerman. After that I was a Simons Postdoctoral Fellow at University of Washington. Previously I worked a little on quantum computing and human computer interaction. Here is my recent research statement.
I am supported by the following grants:
NSF Award CCF-1617713
Johns Hopkins Catalyst Award
NSF CAREER Award CCF-1845349
I am co-organizing the theory seminar at CS@JHU. If you are interested in giving a talk here, send me an email!
Past and Current Group Members
Program Committee
51st ACM Symposium on Theory of Computing (STOC 2019)
8th and 9th nternational Conference on Advanced Communications and Computation (INFOCOMP 2018, 2019)
19th International Workshop on Randomization and Computation (RANDOM 2015)
11th International Conference on Information Security and Cryptology (Inscrypt 2015)
Teaching
Publications
- Xin Li and Yan Zhong
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs (ArXiv 2023).
- Xin Li
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More (FOCS 2023, to appear).
- Alex 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 (CCC 2023).
- Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei and Yu Zheng
Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes (ICALP 2023).
- Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro
Low-Degree Polynomials Extract from Local Sources (ICALP 2022).
- Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang
Improved Decoding of Expander Codes (ITCS 2022).
- Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions (FOCS 2021).
- Xin Li and 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 and Yu Zheng
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence (ICALP 2021).
- Chu-Cheng Lin, Aaron Jaech, Xin Li, Matt Gormley and Jason Eisner
Autoregressive Modeling is Misspecified for Some Sequence Distributions (NAACL 2021).
- Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler and Xin Li
Efficient Linear and Affine Codes for Correcting Insertions/Deletions (SODA 2021).
- Kuan Cheng and Xin Li
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information (SODA 2021).
- Eshan Chattopadhyay and Xin Li
Non-Malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering (TCC 2020).
- Xin Li, Fermi Ma, Willy Quach and Daniel Wichs
Leakage-Resilient Key Exchange and Two-Seed Extractors (CRYPTO 2020).
- Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal and Xin Li
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols (FOCS 2020).
- Kuan Cheng, Zhengzhong Jin, Xin Li and Yu Zheng
Space Efficient Deterministic Approximation of String Measures (ArXiv 2020).
- Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal and Xin Li
Extractors for Adversarial Sources via Extremal Hypergraphs (STOC 2020).
- Kuan Cheng, Xin Li and Yu Zheng
Locally Decodable Codes with Randomized Encoding (ArXiv 2020).
- Xin Li
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions (CCC 2019).
- Kuan Cheng, Zhengzhong Jin, Xin Li and 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 and Ke Wu
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets (SODA 2019).
- Kuan Cheng, Zhengzhong Jin, Xin Li and Ke Wu
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors (FOCS 2018).
- Xin Li, Shachar Lovett and Jiapeng Zhang
Sunflowers and Quasi-sunflowers from Randomness Extractors (RANDOM 2018).
Invited to Theory of Computing Special Issue of RANDOM 2018.
- Kuan Cheng and Xin Li
Randomness Extraction in AC0 and with Small Locality (RANDOM 2018).
- Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li and Amnon Ta-Shma
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate (CCC 2018).
- Kuan Cheng, Yuval Ishai and Xin Li
Near-Optimal Secret Sharing and Error Correcting Codes in AC0 (TCC 2017).
- Eshan Chattopadhyay and Xin Li
Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions (STOC 2017).
- Xin Li
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors (STOC 2017).
- Eshan Chattopadhyay and Xin Li
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols (FOCS 2016).
- Xin Li
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy (FOCS 2016).
- Amitabh Basu, Michael Dinitz and Xin Li
Computing approximate PSD factorizations (Approx 2016).
- Eshan Chattopadhyay and Xin Li
Extractors for Sumset Sources (STOC 2016).
- Eshan Chattopadhyay, Vipul Goyal and Xin Li
Non-Malleable Extractors and Codes, with their Many Tampered Extensions (STOC 2016).
- Xin Li
Three-Source Extractors for Polylogarithmic Min-Entropy (FOCS 2015).
- Xin Li
Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification (TCC 2015).
- Kai-Min Chung, Xin Li and Xiaodi Wu
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications (ECCC 2014).
- Xin Li
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy (FOCS 2013).
Invited to SICOMP Special Issue of FOCS 2013.
- Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai and David Zuckerman
Robust Pseudorandom Generators (ICALP 2013).
- Xin Li
New Independent Source Extractors with Exponential Improvement (STOC 2013)
- Xin Li
Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification (FOCS 2012)
- Xin Li
Design Extractors, Non-Malleable Condensers and Privacy Amplification (STOC 2012)
- Ph.D. Thesis
- Yevgeniy Dodis, Xin Li, Trevor D. Wooley and David Zuckerman
Privacy Amplification and Non-Malleable Extractors Via Character Sums (FOCS 2011)
SICOMP Special Issue of FOCS 2011.
- Xin Li
Improved Constructions of Three Source Extractors (CCC 2011)
- Xin Li
On the Problem of Local Randomness in Privacy Amplification with an Active Adversary (Arxiv 2010:1011.2551)
- Xin Li
A New Approach to Affine Extractors and Dispersers (CCC 2011)
- Yael Tauman Kalai, Xin Li and Anup Rao
2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness (FOCS 2009)
- Yael Tauman Kalai, Xin Li, Anup Rao and David Zuckerman
Network Extractor Protocols (FOCS 2008)
- Runyao Duan, Yuan Feng, Xin Li and Mingsheng Ying
Multiple-copy entanglement transformation and entanglement
catalysis (Physical Review A 2005)
- Runyao Duan, Yuan Feng, Xin Li and Mingsheng Ying
Trade-off between multiple-copy transformation and
entanglement catalysis (Physical Review A 2005)
- Xin Li, Luo Sun, Linmi Tao, Guangyou Xu and Ying Jia
A Speaker Tracking Algorithm Based on Audio and Visual
Information Fusion Using Particle Filter (ICIAR 2004)
Biography
I came to the U.S. for my Ph.D. study after completing my B.S. and M.S. at the CS Department of Tsinghua University, Beijing, China.