8 citations · 41 across the 26 of their papers we have counts for
4 papers · 1 filter
A faster and simpler algorithm for learning shallow networks
Sitan Chen, Shyam Narayanan
We revisit the well-studied problem of learning a linear combination of ReLU activations given labeled examples drawn from the standard -dimensional Gaussian measure. Chen e…
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Anders Aamand, Justin Y. Chen, Piotr Indyk +5
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph…
Almost Tight Approximation Algorithms for Explainable Clustering
Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal…
Learning-based Support Estimation in Sublinear Time
Talya Eden, Piotr Indyk, Shyam Narayanan +3
We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a ra…