Ning Xie

I have completed my Ph.D. studies under the supervison of Prof. Ronitt Rubinfeld
and recently moved to Florida

Schedule for the Algorithms and Complexity Seminar (A&C Seminar) of Spring 2008

Online Publications

  1. Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie
    Converting online algorithms to local computation algorithms.
    ICALP 2012, pp. 653-664.
    [Pdf]; arXiv

  2. Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie
    Space-efficient local computation algorithms.
    SODA 2012, pp. 1132-1139.
    [Pdf]; arXiv

  3. Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie
    The complexity of linear dependence problems in vector spaces.
    ICS 2011, pp. 496-508.

  4. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie
    Fast local computation algorithms.
    ICS 2011, pp. 223-238.
    [Pdf]; arXiv

  5. Victor Chen, Madhu Sudan, Ning Xie
    Property testing via set-theoretic operations.
    ICS 2011, pp. 211-222.

  6. Arnab Bhattacharyya, Ning Xie
    Lower bounds for testing triangle-freeness in Boolean functions.
    SODA 2010, pp. 87-98.

  7. Ronitt Rubinfeld, Ning Xie
    Testing non-uniform k-wise independent distributions over product spaces.
    Random Structures and Algorithms, to appear (Preliminary version in ICALP 2010, pp. 565-581).

  8. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
    Testing linear-invariant non-linear properties.
    Theory of Computing, 7:75-99, 2011 (Preliminary version in STACS 2009, pp. 135-146).

  9. Tali Kaufman, Simon Litsyn, Ning Xie
    Breaking the epsilon-soundness bound of the linearity test over GF(2).
    SIAM Journal on Computing, 39(5):1988-2003, 2010 (Preliminary version in RANDOM 2008, pp. 275-284).

  10. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie
    Testing k-wise and almost k-wise independence.
    STOC 2007, pp. 496-505.