54 citations · 88 across the 15 of their papers we have counts for
6 papers · 1 filter
A New Algorithm for Finding Closest Pair of Vectors
Ning Xie, Shuai Xu, Yekun Xu
Given vectors in , how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the \emph{Closest Pair…
Sunflowers and Testing Triangle-Freeness of Functions
Ishay Haviv, Ning Xie
A function is triangle-free if there are no satisfying and . In tes…
Converting online algorithms to local computation algorithms
Yishay Mansour, Aviad Rubinstein, Shai Vardi +1
We propose a general method for converting online algorithms to local computation algorithms by selecting a random permutation of the input, and simulating running the online algor…
Space-efficient Local Computation Algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi +1
Recently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called \emph{local computation algorithms}. In this model, a computation problem …
Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi +1
For input , let denote the set of outputs that are the "legal" answers for a computational problem . Suppose and members of are so large that there is not t…
Property Testing via Set-Theoretic Operations
Victor Chen, Madhu Sudan, Ning Xie
Given two testable properties and , under what conditions are the union, intersection or set-difference of these two properties also testable? We…