dxiao

email:

@lri.fr

snail mail:

David Xiao
Bat. 490
Université Paris-Sud
91405 Orsay
France

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


About Me

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

Here is my CV [PS, PDF].

Publications

Complexity

  • "A constant-round public-coin protocol for sampling with size, and applications " [Abs, Bib, PS, PDF]
    I. Haitner, M. Mahmoody-Ghidary, and D. Xiao. Princeton Technical Report TR-867-09, 2009.
  • "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.
  • "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

  • "(Nearly) optimal black-box constructions of commitments secure against selective opening attacks " [Abs, Bib, PS, PDF]
    D. Xiao. Manuscript 2009.
  • "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. Manuscript 2009.
  • "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

Graph theory

  • "The Evolution of Expander Graphs " [Abs, Bib,PS, PDF]
    D. Xiao, AB thesis, Harvard College 2003

Miscellaneous

  • "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