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].

Please note: I am currently on leave and am not responding to requests for internships or doctoral candidates. You may contact another member of our group here.


The list below is out of date. For the most complete list of my publications, please refer to DBLP.


  • "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. To appear, 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. To appear, 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