Ning Xie's Online Publications

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

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
AC^{0} ○ MOD_{2} lower bounds for the Boolean Inner Product.
Journal of Computer and System Sciences, 97:4559, 2018
(Preliminary version in ICALP 2016, pp. 35:135:14).
[Pdf]

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

Ishay Haviv, Ning Xie
Sunflowers and testing trianglefreeness of functions.
Computational Complexity, 26(2), 497530, 2017 (Preliminary version in ITCS 2015, pp. 357366).
[Pdf]

Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang
Fourier sparsity, spectral norm, and the Logrank conjecture.
FOCS 2013, pp. 658667.
[Pdf]

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

Testing kwise Independent Distributions.
PhD thesis.
[Pdf]

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

Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie
Spaceefficient local computation algorithms.
SODA 2012, pp. 11321139.
[Pdf];
arXiv

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

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

Victor Chen, Madhu Sudan, Ning Xie
Property testing via settheoretic operations.
ICS 2011, pp. 211222.
[Pdf]

Arnab Bhattacharyya, Ning Xie
Lower bounds for testing trianglefreeness in Boolean functions.
Computational Complexity, 24(1):65101, 2015 (Preliminary version in SODA 2010, pp. 8798).
[Pdf]

Ronitt Rubinfeld, Ning Xie
Robust characterizations of kwise independence over product
spaces and related testing results.
Random Structures and Algorithms, 43(3):265312, 2013
(Preliminary version, titled "Testing nonuniform
kwise independent distributions over product spaces", in ICALP 2010, pp. 565581).
[Pdf]

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
Testing linearinvariant nonlinear properties.
Theory of Computing, 7:7599, 2011 (Preliminary
version in STACS 2009, pp. 135146).
[Pdf]

Tali Kaufman, Simon Litsyn, Ning Xie
Breaking the epsilonsoundness bound of the linearity test over GF(2).
SIAM Journal on Computing, 39(5):19882003, 2010 (Preliminary version in RANDOM 2008, pp. 275284).
[Pdf]

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie
Testing kwise and almost kwise independence.
STOC 2007, pp. 496505.
[Pdf]