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

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.
SODA 2010, pp. 8798.
[Pdf]

Ronitt Rubinfeld, Ning Xie
Testing nonuniform kwise independent distributions over product spaces.
Random Structures and Algorithms, to appear (Preliminary version 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]