snail mail:

David Xiao
Université Paris Diderot - Paris 7
Case 7014
75205 Paris Cedex 13

English | Français | 中文 | עברית

About Me

Welcome to my home page. I am a CNRS researcher in the Algorithms and Complexity Group at LIAFA, focusing on complexity theory and cryptography. Prior to coming here, I obtained my Ph. D from Princeton University under the co-supervision of Boaz Barak and Avi Wigderson (IAS).

Here is my CV [PS, PDF].

On leave:I am currently on leave from the CNRS and building Gift Uncommon.



  • "Lower bounds on information complexity via zero-communication protocols and applications"
    [Abs, Bib, PS, PDF]

    I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. FOCS 2012.
  • "Improved bounds for the randomized decision tree complexity of recursive majority"
    [Abs, Bib, PS, PDF]

    F. Magniez, A. Nayak, M. Santha, and D. Xiao. ICALP 2011.
  • "Learning to create is as hard as learning to appreciate"
    [Abs, Bib, PS, PDF]

    D. Xiao. COLT 2010.
  • "A new sampling protocol and applications to basing cryptographic primitives on NP"
    [Abs, Bib, PS, PDF]

    I. Haitner, M. Mahmoody, and D. Xiao. CCC 2010
  • "On the power of randomized reductions and the checkability of SAT"
    [Abs, Bib, PS, PDF]

    M. Mahmoody, and D. Xiao. CCC 2010
  • "On basing ZK != BPP on the hardness of PAC learning"
    [Abs, Bib,PS, PDF]

    D. Xiao. CCC 2009.
  • "On basing lower-bounds for learning on worst-case assumptions"
    [Abs, Bib, PS, PDF]

    B. Applebaum, B. Barak, D. Xiao. FOCS 2008
  • "Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators and applications"
    [Abs, Bib, PS, PDF]

    A. Wigderson and D. Xiao, Theory of Computing, Vol. 4 #3 (2008)
  • "A randomness-efficient sampler for matrix-valued functions and applications"
    [Abs, Bib, PS, PDF]

    A. Wigderson and D. Xiao, FOCS 2005

Cryptography and Security

  • "Languages with efficient Zero Knowledge PCPs are in SZK "
    [Abs, Bib, PS, PDF]

    M. Mahmoody and D. Xiao. TCC 2013.
  • "Round-optimal black-box statistically binding selective-opening secure commitments"
    [Abs, Bib, PS, PDF]

    D. Xiao. AFRICACRYPT 2012.
  • "Is privacy compatible with truthfulness?"
    [Abs, Bib, PS, PDF]

    D. Xiao. ITCS 2013. First appeared as Cryptology ePrint Technical Report, 2011/005, 2011.
  • "On the round complexity of black-box constructions of commitments secure against selective opening attacks"
    [Abs, Bib, PS, PDF]

    D. Xiao. Cryptology ePrint Technical Report 2009/513, 2012. Preliminary version appeared in TCC 2011. [Bib]
  • "On the round complexity of zero-knowledge proofs from one-way permutations"
    [Abs, Bib, PS, PDF]

    S. Gordon, H. Wee, D. Xiao, and A. Yerukhimovich. LATINCRYPT 2010.
  • "Path-quality monitoring in the presence of adversaries"
    [Abs, Bib,PS, PDF]

    S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford. SIGMETRICS 2008
  • "Protocols and lower bounds for failure localization in the Internet"
    [Abs, Bib,PS, PDF]

    B. Barak, S. Goldberg, and D. Xiao. EUROCRYPT 2008

Surveys and Theses

  • "Pseudo-aléa: objets et génération" (français)
    [Abs, Bib,PS, PDF]

    D. Xiao. Journées annuelles de la Société Mathématiques de France, 2011
  • "New Perspectives on the Complexity of Computational Learning, and Other Problems in Theoretical Computer Science" [Abs, Bib, PS, PDF]
    D. Xiao. Ph. D thesis. Princeton University, 2009.
  • "The Evolution of Expander Graphs"
    [Abs, Bib,PS, PDF]

    D. Xiao. AB thesis, Harvard College 2003


  • "Estimating and comparing entropy across written natural languages using PPM compression",
    [Abs, Bib,PS, PDF]

    F. Behr, V. Fossum, M. Mitzenmacher, D. Xiao, Data Compression Conference 2003