Ying Xu   Dept of Computer Science Stanford University Stanford, CA 94305 Office: Gates 470 Phone: 650-723-1787 Email: xuying at stanford dot edu

I am a fifth year Ph.D. student in the Computer Science Dept of Stanford University ,
working with Prof. Rajeev Motwani.
I am interested in randomized algorithms, web, database and data privacy.

resume   publications    bio-software I wrote   personal

Publications

• Stochastic Kronecker Graphs.  full version   conference version
  5th Workshop on Algorithms and Models for the Web-Graph (WAW) 2007.
  (with Mohammad Mahdian)

• Searchability in random graphs.
  5th Workshop on Algorithms and Models for the Web-Graph (WAW) 2007.
  (with E. Arcaute, N. Chen, R. Kumar, D. Liben-Nowell, M. Mahdian and H. Nazerzadeh)

• Estimating Sum by Weighted Sampling.
  34th International Colloquium on Automata, Languages and Programming (ICALP) 2007.
  (with Rajeev Motwani, Rina Panigrahy)

• Efficient Algorithms for Masking and Finding Quasi Identifiers.
  Technical Report.
  (with Rajeev Motwani)

• Evolution of Page Popularity under Random Web Graph Models.
  25th ACM Principles of Database Systems (PODS) 2006.
  (with Rajeev Motwani)

• Fractional Matching via Balls-and-Bins.
  10th International Workshop on Randomization and Computation (RANDOM) 2006.
  (with Rajeev Motwani, Rina Panigrahy)

• Estimating corpus size via queries.
  ACM 15th Conference on Information and Knowledge Management (CIKM) 2006.
  (with A. Broder, M. Fontoura, V. Josifovski, R. Kumar, R. Motwani, R. Panigrahy, S. Nabar, A. Tomkins)

• Efficient probabilistic algorithms for detecting pairs of fuzzy duplicates.
  Microsoft Technical Report.
  (with Venky Ganti)

• Two Can Keep A Secret: A Distributed Architecture for Secure Database Services.
  2nd Conference on Innovative Data Systems Research (CIDR) 2005.
  (with G.Aggarwal, M.Bawa, P.Ganesan, H.Garcia-Molina, K.Kenthapadi, R.Motwani, U.Srivastava, D.Thomas)

• Vision Paper: Enabling Privacy for the Paranoids.
  30th International Conference on Very Large Data Bases (VLDB) 2004.
  (with G.Aggarwal, M.Bawa, P.Ganesan, H.Garcia-Molina, K.Kenthapadi, N.Mishra, R.Motwani, U.Srivastava, D.Thomas, J.Widom)

• Exact matching of RNA secondary structure patterns
  2nd conference on Asia-Pacific bioinformatics, 2004; also in Theor. Comput. Sci. 335, 2005.
  (with Lusheng Wang, Xiaotie Deng)

• An O(n^1.5) deterministic gossiping algorithm for radio networks
  Algorithmica, 36, 2003

• SEGID: identifying interesting segments in sequence alignments
  Bioinformatics, 19(2), 2003.
  (with Lusheng Wang)

• A greedy method for inferring tandem duplication history
  Bioinformatics, 19(12), 2003.
  (with Lusheng Zhang, Bin Ma, Lusheng Wang)

• Haplotype Inference by Parsimony
  Bioinformatics, 19(14), 2003.
  (with Lusheng Wang)