Ning Xie's Online Publications

  1. Ning Xie, Shuai Xu, Yekun Xu
    A new coding-based algorithm for finding closest pair of vectors.
    Theoretical Computer Science, to appear (Preliminary version in CSR 2018, pp. 321-333).
    [Pdf]

  2. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
    AC0 ○ MOD2 lower bounds for the Boolean Inner Product.
    Journal of Computer and System Sciences, 97:45-59, 2018 (Preliminary version in ICALP 2016, pp. 35:1-35:14).
    [Pdf]

  3. Hing Yin Tsang, Ning Xie, Shengyu Zhang
    Fourier sparsity of GF(2) polynomials.
    CSR 2016, pp. 409-424.
    [Pdf]

  4. Ishay Haviv, Ning Xie
    Sunflowers and testing triangle-freeness of functions.
    Computational Complexity, 26(2), 497-530, 2017 (Preliminary version in ITCS 2015, pp. 357-366).
    [Pdf]

  5. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang
    Fourier sparsity, spectral norm, and the Log-rank conjecture.
    FOCS 2013, pp. 658-667.
    [Pdf]

  6. Elena Grigorescu, Karl Wimmer, Ning Xie
    Tight lower bounds for testing linear isomorphism.
    RANDOM 2013, pp. 559-574.
    [Pdf]

  7. Testing k-wise Independent Distributions.
    PhD thesis.
    [Pdf]

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

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

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

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

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

  13. Arnab Bhattacharyya, Ning Xie
    Lower bounds for testing triangle-freeness in Boolean functions.
    Computational Complexity, 24(1):65-101, 2015 (Preliminary version in SODA 2010, pp. 87-98).
    [Pdf]

  14. Ronitt Rubinfeld, Ning Xie
    Robust characterizations of k-wise independence over product spaces and related testing results.
    Random Structures and Algorithms, 43(3):265-312, 2013
    (Preliminary version, titled "Testing non-uniform k-wise independent distributions over product spaces", in ICALP 2010, pp. 565-581).
    [Pdf]

  15. 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).
    [Pdf]

  16. 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).
    [Pdf]

  17. 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.
    [Pdf]