Skip to main content

Li, Xin

Associate Professor
Computer Science
https://www.cs.jhu.edu/~lixints/

Malone 215
(410) 516-8775
xli113@jhu.edu

Jump to:

News

About

Education
  • Ph.D. 2011, Univ Texas Austin*
  • Master of Science 2005, Tsinghua University
  • Bachelor of Science 2002, Tsinghua University
Experience
  • 2011 - 2013:  Postdoctoral Research Associate, University of Washington
Research Areas
  • CODING theory
  • Complexity theory
  • Cryptography
  • DISTRIBUTED computing
  • Randomness in computation
  • Theory of computation
Presentations
  • "Recent Progress on Explicit Constructions of Randomness Extractors", Chinese Academy of Sciences, Beijing, China.  November 24, 2017
  • "Three Source Extractors for Polylogarithmic Min-Entropy, with quantum sideinformation", International Workshop on Quantum Computing and Quantum Information Processing(QCQIP 2017).  November 21, 2017
  • "Randomness Extractors and their applications", Institute for Theoretical Computer Science, Shanghai University of Finance and Economics,China.  September 21, 2016
  • "Randomness Extractors and their applications", Shanghai Jiaotong University, China.  September 15, 2016
  • "Almost Optimal Non-Malleable Extractors and Privacy Amplification Protocol", The IMS Workshop on Mathematics of Information Theoretic Cryptography, Singapore.  September 9, 2016
  • "Almost Optimal Non-Malleable Extractors and Privacy Amplification Protocols", DIMACS Workshop on Cryptography and Its Interactions.  July 10, 2016
  • "Almost Optimal Non-Malleable Extractors and Privacy Amplification Protocols", Capital Area Theory Day.  May 12, 2016
  • "Recent Developments in Explicit Constructions of Randomness Extractors", 2016 Joint Mathematics Meetings.  Seattle, WA.  January 8, 2016
  • "Three-Source Extractors for Polylogarithmic Min-Entropy", 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).  Berkeley, California.  October 18, 2015
  • "Affine Extractors for Polylogarithmic Entropy", Computer Science Theory Seminar.  Austin, TX.  September 12, 2015
  • "Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy", 54th Annual Symposium on Foundations of Computer Science.  Berkeley, California.  October 20, 2013
  • "New Independent Source Extractors with Exponential Improvement", 45th ACM Symposium on Theory of Computing.  June 1, 2013
  • "New Independent Source Extractors with Exponential Improvement", Computer Science/Discrete Math Seminar.  Princeton, NJ.  January 21, 2013
  • "Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification", 53rd Annual IEEE Symposium on Foundations of Computer Science.  New Brunswick, New Jersey.  October 20, 2012
  • "Non-Malleable Extractors, Non-Malleable Condensers and their Applications", 6th International Conference on Information Theoretic Security.  Montreal, Canada.  August 15, 2012
  • "Design Extractors, Non-Malleable Condensers and Privacy Amplification", 44th Annual ACM Symposium on Theory of Computing.  New York, NY.  May 19, 2012
  • "Privacy Amplification and Non-Malleable Extractors Via Character Sums", Microsoft Research Cryptography Colloquium.  Seattle, WA.  November 15, 2011
  • "Privacy Amplification and Non-Malleable Extractors Via Character Sums", 52nd Annual IEEE Symposium on Foundations of Computer Science.  Palm Springs, California.  October 22, 2011
  • "A New Approach to Affine Extractors and Dispersers", China Theory Week.  Beijing, China.  September 12, 2011
  • "A New Approach to Affine Extractors and Dispersers", 26th Annual IEEE Conference on Computational Complexity.  San Jose, California.  June 8, 2011
  • "Improved Constructions of Three Source Extractors", 26th Annual IEEE Conference on Computational Complexity.  San Jose, California.  June 8, 2011
  • "Improved Constructions of Three Source Extractors", Computational Complexity of Discrete Problems.  Leibniz-Zentrum für Informatik, Gemany.  March 15, 2011
  • "2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness", 50th Annual IEEE Symposium on Foundations of Computer Science.  Atlanta, Georgia.  October 24, 2009
  • "Network Extractor Protocols", 49th Annual IEEE Symposium on Foundations of Computer Science.  Philadelphia, Pennsylvania.  October 25, 2008

Publications

Journal Articles
  • Chattopadhyay E, Goodman J, Goyal V, Li X (2020).  Extractors for adversarial sources via extremal hypergraphs.  Proceedings of the Annual ACM Symposium on Theory of Computing.  1184-1197.
  • Cheng K, Jin Z, Li X, Wu K (2019).  Block edit errors with transpositions: Deterministic document exchange protocols and almost optimal binary codes.  Leibniz International Proceedings in Informatics, LIPIcs.  132.
  • Li X (2019).  Non-malleable extractors and non-malleable codes: Partially optimal constructions.  Leibniz International Proceedings in Informatics, LIPIcs.  137.
  • Cheng K, Haeupler B, Li X, Shahrasbi A, Wu K (2019).  Synchronization strings: Highly efficient deterministic constructions over small alphabets.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.  2185-2204.
  • Cheng K, Jin Z, Li X, Wu K (2018).  Deterministic document exchange protocols, and almost optimal binary codes for edit errors.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  2018-October.  200-211.
  • Cheng K, Li X (2018).  Randomness extraction in AC0 and with small locality.  Leibniz International Proceedings in Informatics, LIPIcs.  116.
  • Li X, Lovett S, Zhang J (2018).  Sunflowers and quasi-sunflowers from randomness extractors.  Leibniz International Proceedings in Informatics, LIPIcs.  116.
  • Ben-Aroya A, Chattopadhyay E, Doron D, Li X, Ta-Shma A (2018).  A new approach for constructing low-error, two-source extractors.  Leibniz International Proceedings in Informatics, LIPIcs.  102.  31-319.
  • Chattopadhyay E, Li X (2017).  Non-malleable codes and extractors for small-depth circuits, and affine functions.  Proceedings of the Annual ACM Symposium on Theory of Computing.  Part F128415.  1171-1184.
  • Li X (2017).  Improved non-malleable extractors, non-malleable codes and independent source extractors.  Proceedings of the Annual ACM Symposium on Theory of Computing.  Part F128415.  1144-1156.
  • Cheng K, Ishai Y, Li X (2017).  Near-optimal secret sharing and error correcting codes in AC0.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  10678 LNCS.  424-458.
  • Chattopadhyay E, Li X (2016).  Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  2016-December.  158-167.
  • Li X (2016).  Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  2016-December.  168-177.
  • Basu A, Dinitz M, Li X (2016).  Computing approximate PSD factorizations.  Leibniz International Proceedings in Informatics, LIPIcs.  60.
  • Chattopadhyay E, Li X (2016).  Extractors for sumset sources.  Proceedings of the Annual ACM Symposium on Theory of Computing.  19-21-June-2016.  299-311.
  • Chattopadhyay E, Goyal V, Li X (2016).  Non-malleable extractors and codes, with their many tampered extensions.  Proceedings of the Annual ACM Symposium on Theory of Computing.  19-21-June-2016.  285-298.
  • Li X (2015).  Three-Source Extractors for Polylogarithmic Min-Entropy.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  2015-December.  863-882.
  • Li X (2015).  Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  9014.  502-531.
  • Dodis Y, Li X, Wooley TD, Zuckerman D (2014).  Privacy amplification and nonmalleable extractors via character sums.  SIAM Journal on Computing.  43(2).  800-830.
  • Dodis Y, Li X, Wooley TD, Zuckerman D (2014).  Privacy amplification and nonmalleable extractors via character sums.  SIAM Journal on Computing.  43(2).  800-830.
  • Li X (2013).  Extractors for a constant number of independent sources with polylogarithmic min-entropy.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  100-109.
  • Ishai Y, Kushilevitz E, Li X, Ostrovsky R, Prabhakaran M, Sahai A, Zuckerman D (2013).  Robust pseudorandom generators.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7965 LNCS(PART 1).  576-588.
  • Li X (2013).  New independent source extractors with exponential improvement.  Proceedings of the Annual ACM Symposium on Theory of Computing.  783-792.
  • Li X (2012).  Non-malleable extractors, two-source extractors and privacy amplification.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  688-697.
  • Li X (2012).  Design extractors, non-malleable condensers and privacy amplification.  Proceedings of the Annual ACM Symposium on Theory of Computing.  837-854.
  • Dodis Y, Li X, Wooley TD, Zuckerman D (2011).  Privacy amplification and non-malleable extractors via character sums.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  668-677.
  • Li X (2011).  Improved constructions of three source extractors.  Proceedings of the Annual IEEE Conference on Computational Complexity.  126-136.
  • Li X (2011).  A new approach to affine extractors and dispersers.  Proceedings of the Annual IEEE Conference on Computational Complexity.  137-147.
  • Kalai YT, Li X, Rao A (2009).  2-source extractors under computational assumptions and cryptography with defective randomness.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  617-626.
  • Kalai YT, Xin L, Rao A, Zuckerman D (2008).  Network extractor protocols.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  654-663.
  • Duan R, Feng Y, Li X, Ying M (2005).  Trade-off between multiple-copy transformation and entanglement catalysis.  Physical Review A - Atomic, Molecular, and Optical Physics.  71(6).
  • Duan R, Feng Y, Li X, Ying M (2005).  Multiple-copy entanglement transformation and entanglement catalysis.  Physical Review A - Atomic, Molecular, and Optical Physics.  71(4).
  • Duan R, Feng Y, Li X, Ying M (2005).  Multiple-copy entanglement transformation and entanglement catalysis.  Physical Review A.  71(4).  042319.
  • Duan R, Feng Y, Li X, Ying M (2005).  Trade-off between multiple-copy transformation and entanglement catalysis.  Physical Review A.  71(6).  062306.
  • Li X, Sun L, Tao L, Xu G, Jia Y (2004).  A speaker tracking algorithm based on audio and visual information fusion using particle filter.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  3212.  572-580.
Book Chapters
  • Li X, Sun L, Tao L, Xu G, Jia Y (2004).  A speaker tracking algorithm based on audio and visual information fusion using particle filter.  Image Analysis and Recognition.  Springer.  572-580.
Other Publications
  • Li X, Chung K, Wu X (2016).  Multi-Source Randomness Extractors Against Quantum Side Information.
  • Li X, Cheng K  Randomness Extraction in AC0 and with Small Locality.
Conference Proceedings
  • Ishai Y, Kushilevitz E, Li X, Ostrovsky R, Prabhakaran M, Sahai A, Zuckerman D (2013).  Robust pseudorandom generators.  Automata, Languages, and Programming.  Springer.  576-588.
  • Kalai YT, Li X, Rao A (2009).  2-source extractors under computational assumptions and cryptography with defective randomness.  Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on.  617-626.
  • Kalai YT, Li X, Rao A, Zuckerman D (2008).  Network extractor protocols.  Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on.  654-663.
  • Li X, Runyao Duan, Yuan Feng, Mingsheng Ying (2005).  Multiple-copy entanglement transformation and entanglement catalysis.  Physical Review A.
  • Li X, Runyao Duan, Yuan Feng, Mingsheng Ying (2005).  Trade-off between multiple-copy transformation and entanglement catalysis.  Physical Review A.
Back to top